University:
Boston University
Course:
CAS CS 501 | Computer Science Practicum
Academic year:

2022
Views:

258

Pages:

12
Author:

Charlize Mccoy

Basics of Network Analysis Graph = Network • G(V, E): graph (network) V: vertices (nodes), E: edges (links) 1 Nodes = 1, 2, 3, 4, 5 3 2 4 5 Links = 1<->2, 1<->3, 1<->5, 2<->3, 2<->4, 2<->5, 3<->4, 3<->5, 4<->5 (Nodes may have states; links may have directions and weights) Representation of a network • Adjacency matrix: A matrix with rows and columns labeled by nodes, where element aij shows the number of links going from node i to node j (becomes symmetric for undirected graph) • Adjacency list: A list of links whose element “i->j” shows a link going from node i to node j (also represented as “i -> {j1, j2, j3, …}”) Exercise • Represent the following network in: 1 – Adjacency matrix 3 2 4 5 – Adjacency list Degree of a node • A degree of node u, deg(u), is the number of links connected to u u1 deg(u1) = 4 u2 deg(u2) = 2 Connected graph • A graph in which there is a path between any pair of nodes Connected components Number of connected components = 2 Connected component Connected component Complete graph • A graph in which any pair of nodes are connected (often written as K1, K2, …) Regular graph • A graph in which all nodes have the same degree (often called k-regular graph with degree k) Bipartite graph • A graph whose nodes can be divided into two subsets so that no link connects nodes within the same subset = Directed graph • Each link is directed • Direction represents either order of relationship or accessibility between nodes E.g. genealogy Weighted directed graph • Most general version of graphs • Both weight and direction is assigned to each link E.g. traffic network