Report

CS8803-NS Network Science Fall 2013 Instructor: Constantine Dovrolis constantine@gatech.edu http://www.cc.gatech.edu/~dovrolis/Courses/NetSci/ Disclaimers The following slides include only the figures or videos that we use in class; they do not include detailed the explanations, derivations or descriptions covered in class. Many of the following figures are copied from open sources at the Web. I do not claim any intellectual property for the following material. Outline • Basic concepts – – – – – Graphs, paths, adjacency matrix, etc Centrality metrics Clustering metrics Cliques and cores Assortativity metrics • Weighted networks – Application paper: airline networks • Spatial networks – Application paper: city networks • More about betweenness centrality – Betweenness centrality algorithm by Brandes – Mini-talk by Oded Green about parallel/streaming BC computation • Surprise “visitor” will talk about Network Medicine Undirected, directed, weighted graphs Graph adjacency matrix http://sourcecodemania.com/wp-content/uploads/2012/06/adjacency-matrix-of-graph.jpg Graph adjacency matrix (cont’) • Many network properties can be formulated as properties of the adjacency matrix – See “algebraic graph theory” • For instance: – A directed network is acyclic if and only if all eigenvalues of the adjacency matrix are equal to 0 • Proof? Planar graphs http://people.hofstra.edu/geotrans/eng/methods/img/planarnonplanar.png • Here is an example of a famous graph theory result: – Kuratowski: Every non-planar graph contains at least one subgraph that is an expansion of a 5-node clique or of the “utility graph” K3,3 (shown at the top right) Node degree, in-out degrees, degree distribution k’th moment • Directed graphs: aij=1 if edge from i to j Degree distribution http://1.bp.blogspot.com/-QJTJS8wcdtg/T5rio1NHPvI/AAAAAAAAAq8/umNpggK8VAY/s400/p1.png Average degree, connectance, sparse and dense graphs • Undirected graph with n nodes and m edges • Average node degree: c = 2*m / n • Connectance: ρ = c / (n-1) • What happens to ρ as n tends to infinity? • Sparse graphs: ρ tends to zero • Dense graphs: ρ tends to positive constant Paths, Shortest Paths, Diameter, Characteristic Path Length, Graph Efficiency Paths and their length a b d c http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture2/Images/A2.gif • Number of paths of length r from j to i: Nij(r)=[Ar]ij Cyclic and Acyclic graphs http://upload.wikimedia.org/wikipedia/commons/thumb/3/39/Directed_acyclic_graph_3.svg/356pxDirected_acyclic_graph_3.svg.png • Number of loops of length r anywhere in network: L(r) = Σi[Ar] ii = Tr[Ar] = Σi[kir] – ki eigenvalue of adjacency matrix – Proof? Easier for undirected networks Eulerian and Hamiltonian graphs http://www.transtutors.com/Uploadfile/CMS_Images/10131_Hamiltonian%20Graphs.JPG Weakly Connected Components & Strongly Connected Components http://media.tumblr.com/tumblr_m0oeu763ds1qir7tc.png Min-cut and max-flow http://scienceblogs.com/goodmath/wp-content/blogs.dir/476/files/2012/04/id36ecaca5a38da5705e2e708e6d84070-max-flow.png • For a given (source, sink) pair: the max flow between them is the sum of the weights of the edges of the min-cut-set that separates (source, sink) Network centrality metrics http://www-personal.umich.edu/~mejn/centrality/labeled.png http://www.isearchm.com/wp-content/uploads/2012/05/networks.jpg We will talk later about centrality metrics for directed networks, such as PageRank or HITS Cliques, plexes and cores • Clique of size n: maximal subset of nodes, with every node connected to every other member of the subset • k-plex of size n: maximal subset of nodes, with every node connected to at least n-k other members of the subset – k=1: clique – k>1: “approximate clique” • k-core of size n: maximal subset of nodes, with every node connected to at least k others in the subset K-core decomposition http://www.nature.com/srep/2012/120420/srep00371/images/srep00371-f1.jpg Transitivity & Clustering coeff Clustering coefficient http://www.emeraldinsight.com/fig/202_10_1108_S1479-361X_2012_0000010012.png Degree correlations In general, is knn(k) increasing/decreasing with k? Assortativity – Degree mixing http://stepsandleaps.files.wordpress.com/2013/08/assortative_disassortative.jpg?w=450&h=235 How would you classify social networks in this axis? Technological networks such as the Internet? Core-periphery networks (“rich club” network) http://km4meu.files.wordpress.com/2009/11/core-periphery-ross-mayfield1.jpg Outline • Basic concepts – – – – – Graphs, paths, adjacency matrix, etc Centrality metrics Clustering metrics Cliques and cores Assortativity metrics • Weighted networks – Application paper: airline networks • Spatial networks – Application paper: city networks • More about betweenness centrality – Betweenness centrality algorithm by Brandes – Mini-talk by Oded Green about parallel/streaming BC computation • Surprise “visitor” will talk about Network Medicine Node strength Strength distribution Relation between strength and degree Weighted clustering coefficient Weighted average neighbors degree Outline • Basic concepts – – – – – Graphs, paths, adjacency matrix, etc Centrality metrics Clustering metrics Cliques and cores Assortativity metrics • Weighted networks – Application paper: airline networks • Spatial networks – Application paper: city networks • More about betweenness centrality – Betweenness centrality algorithm by Brandes – Mini-talk by Oded Green about parallel/streaming BC computation • Surprise “visitor” will talk about Network Medicine Spatial networks • Nodes are embedded in physical space (2d or 3d) • Edges have physical length • Planar graphs constraint • Spatial embedding affects maximum degree or maximum edge length • Spatial networks vs Relational networks Analyzed one-square-mile maps from 18 cities Food for thought • How do you explain the (major) difference in the distributions of betweenness centrality and information centrality? – What is a good generative model for selforganized cities? • How would you cluster similar cities together based on their spatial network properties? Outline • Basic concepts – – – – – Graphs, paths, adjacency matrix, etc Centrality metrics Clustering metrics Cliques and cores Assortativity metrics • Weighted networks – Application paper: airline networks • Spatial networks – Application paper: city networks • More about betweenness centrality – Betweenness centrality algorithm by Brandes – Mini-talk by Oded Green about parallel/streaming BC computation • Surprise “visitor” will talk about Network Medicine Counting shortest paths Accumulation of path-dependencies Mini-talk by Oded Green about parallel, streaming BC computation Outline • Basic concepts – – – – – Graphs, paths, adjacency matrix, etc Centrality metrics Clustering metrics Cliques and cores Assortativity metrics • Weighted networks – Application paper: airline networks • Spatial networks – Application paper: city networks • More about betweenness centrality – Betweenness centrality algorithm by Brandes – Mini-talk by Oded Green about parallel/streaming BC computation • Surprise “visitor” will talk about Network Medicine A surprise “visitor” will talk to us about Network Medicine http://www.youtube.com/watch?v=10oQMHa dGos