Question? Leave a message!




graph connectivity and graph traversal

graph connectivity and graph traversal
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Website URL
Comment
3. GRAPHS basic definitions and applications ‣ graph connectivity and graph traversal ‣ testing bipartiteness ‣ connectivity in directed graphs ‣ DAGs and topological ordering ‣ Lecture slides by Kevin Wayne
 Copyright © 2005 Pearson-Addison Wesley
 http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on 1/10/17 10:58 AM3. GRAPHS basic definitions and applications ‣ graph connectivity and graph traversal ‣ testing bipartiteness ‣ connectivity in directed graphs ‣ DAGs and topological ordering ‣Undirected graphs Notation. G = (V, E) V = nodes. E = edges between pairs of nodes. Captures pairwise relationship between objects. Graph size parameters: n = V , m = E . V = 1, 2, 3, 4, 5, 6, 7, 8 E = 1-2, 1-3, 2-3, 2-4, 2-5, 3-5, 3-7, 3-8, 4-5, 5-6, 7-8 
 m = 11, n = 8 3One week of Enron emails 4The evolution of FCC lobbying coalitions “The Evolution of FCC Lobbying Coalitions” by Pierre de Vries in JoSS Visualization Symposium 2010 5The Spread of Obesity in a Large Social Network Over 32 Years educational level; the ego’s obesity status at the ing both their weights. We estimated these mod- previous time point (t); and most pertinent, the els in varied ego–alter pair types. 25 alter’s obesity status at times t and t + 1. We To evaluate the possibility that omitted vari- used generalized estimating equations to account ables or unobserved events might explain the as- for multiple observations of the same ego across sociations, we examined how the type or direc- 26 examinations and across ego–alter pairs. We tion of the social relationship between the ego assumed an independent working correlation and the alter affected the association between the 26,27 structure for the clusters. ego’s obesity and the alter’s obesity. For example, The use of a time-lagged dependent variable if unobserved factors drove the association be- (lagged to the previous examination) eliminated tween the ego’s obesity and the alter’s obesity, serial correlation in the errors (evaluated with a then the directionality of friendship should not 28 Lagrange multiplier test ) and also substantial- have been relevant. ly controlled for the ego’s genetic endowment and We evaluated the role of a possible spread in any intrinsic, stable predisposition to obesity. The smoking-cessation behavior as a contributor to use of a lagged independent variable for an alter’s the spread of obesity by adding variables for the 25 weight status controlled for homophily. The smoking status of egos and alters at times t and key variable of interest was an alter’s obesity at t + 1 to the foregoing models. We also analyzed time t + 1. A significant coefficient for this vari- the role of geographic distance between egos able would suggest either that an alter’s weight and alters by adding such a variable. Framingham heart study affected an ego’s weight or that an ego and an We calculated 95% confidence intervals by sim- alter experienced contemporaneous events affect- ulating the first difference in the alter’s contem- Figure 1. Largest Connected Subcomponent of the Social Network in the Framingham Heart Study in the Year 2000. Each circle (node) represents one person in the data set. There are 2200 persons in this subcomponent of the social network. Circles with red borders denote women, and circles with blue borders denote men. The size of each circle is proportional to the person’s body-mass index. The interior color of the circles indicates the person’s obesity status: yellow denotes an obese person (body-mass index, ≥30) and green denotes a nonobese person. The colors of the ties between the nodes indicate the relationship between them: purple denotes a friendship or marital tie and orange denotes a familial tie. “The Spread of Obesity in a Large Social Network over 32 Years” by Christakis and Fowler in New England Journal of Medicine, 2007 6 373 n engl j med 357;4 www.nejm.org july 26, 2007Some graph applications graph node edge communication telephone, computer fiber optic cable circuit gate, register, processor wire mechanical joint rod, beam, spring financial stock, currency transactions transportation street intersection, airport highway, airway route internet class C network connection game board position legal move social relationship person, actor friendship, movie cast neural network neuron synapse protein network protein protein-protein interaction molecule atom bond 7Graph representation: adjacency matrix Adjacency matrix. n-by-n matrix with A = 1 if (u, v) is an edge. uv Two representations of each edge. 2 Space proportional to n . Checking if (u, v) is an edge takes Θ(1) time. 2 Identifying all edges takes Θ(n ) time. 1 2 3 4 5 6 7 8 1 0 1 1 0 0 0 0 0 2 1 0 1 1 1 0 0 0 3 1 1 0 0 1 0 1 1 4 0 1 0 0 1 0 0 0 5 0 1 1 1 0 1 0 0 6 0 0 0 0 1 0 0 0 7 0 0 1 0 0 0 0 1 8 0 0 1 0 0 0 1 0 8Graph representation: adjacency lists Adjacency lists. Node indexed array of lists. Two representations of each edge. degree = number of neighbors of u Space is Θ(m + n). Checking if (u, v) is an edge takes O(degree(u)) time. Identifying all edges takes Θ(m + n) time. 1 2 3 2 1 3 4 5 8 1 2 5 7 3 4 2 5 5 2 3 4 6 5 6 7 3 8 8 3 7 9Paths and connectivity Def. A path in an undirected graph G = (V, E) is a sequence of nodes
 v , v , …, v with the property that each consecutive pair v , v is joined
 1 2 k i–1 i by an edge in E. Def. A path is simple if all nodes are distinct. Def. An undirected graph is connected if for every pair of nodes u and v, there is a path between u and v. 10Cycles Def. A cycle is a path v , v , …, v in which v = v , k 2, and the first k – 1 1 2 k 1 k nodes are all distinct. cycle C = 1-2-4-5-3-1 11Trees Def. An undirected graph is a tree if it is connected and does not contain a cycle. Theorem. Let G be an undirected graph on n nodes. Any two of the following statements imply the third. G is connected. G does not contain a cycle. G has n – 1 edges. 12Rooted trees Given a tree T, choose a root node r and orient each edge away from r. Importance. Models hierarchical structure. root r parent of v v child of v a tree the same tree, rooted at 1 13Phylogeny trees Describe evolutionary history of species. 14GUI containment hierarchy Describe organization of GUI widgets. http://java.sun.com/docs/books/tutorial/uiswing/overview/anatomy.html 153. GRAPHS basic definitions and applications ‣ graph connectivity and graph traversal ‣ testing bipartiteness ‣ connectivity in directed graphs ‣ DAGs and topological ordering ‣Connectivity s-t connectivity problem. Given two node s and t, is there a path between s and t ? s-t shortest path problem. Given two node s and t, what is the length of the shortest path between s and t ? Applications. Friendster. Maze traversal. Kevin Bacon number. Fewest number of hops in a communication network. 17Breadth-first search BFS intuition. Explore outward from s in all possible directions, adding nodes one "layer" at a time. s L L L 1 2 n–1 BFS algorithm. L = s . 0 L = all neighbors of L . 1 0 L = all nodes that do not belong to L or L , and that have an edge to a 2 0 1 node in L . 1 L = all nodes that do not belong to an earlier layer, and that have an i+1 edge to a node in L . i Theorem. For each i, L consists of all nodes at distance exactly i
 i from s. There is a path from s to t iff t appears in some layer. 18Breadth-first search Property. Let T be a BFS tree of G = (V, E), and let (x, y) be an edge of G.
 Then, the level of x and y differ by at most 1. L 0 L 1 L 2 L 3 19Breadth-first search: analysis Theorem. The above implementation of BFS runs in O(m + n) time if the graph is given by its adjacency representation. Pf. 2 Easy to prove O(n ) running time: at most n lists Li each node occurs on at most one list; for loop runs ≤ n times when we consider node u, there are ≤ n incident edges (u, v),
 and we spend O(1) processing each edge Actually runs in O(m + n) time: when we consider node u, there are degree(u) incident edges (u, v) total time processing edges is Σ degree(u) = 2m. ▪ ∈ u V each edge (u, v) is counted exactly twice
 in sum: once in degree(u) and once in degree(v) 20