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

2020
Views:

60

Pages:

9
Author:

spoelinge93k

Measuring Topological Properties of Networks (3): Mesoscopic Properties Degree correlation (assortativity) • Pearson’s correlation coefficient of node degrees across links Cov(X, Y) r = σX σY • X: degree of start node (in / out) • Y: degree of end node (in / out) Assortative/disassortative networks Social networks are assortative Engineered / biological networks are disassortative K-cores • A connected component of a network obtained by repeatedly deleting all the nodes whose degree is less than k until no more such nodes exist – Helps identify where the core cluster is – All nodes of a k-core have at least degree k – The largest value of k for which a kcore exists is called “degeneracy” of the network Exercise • Find the k-core (with the largest k) of the following network Coreness (core number) • A node’s coreness (core number) is c if it belongs to a c-core but not (c+1)-core • Indicates how strongly the node is connected to the network • Classifies nodes into several layers – Useful for visualization Community • A subgraph of a network within which nodes are connected to each other more densely than to the outside – Still defined vaguely… – Various detection algorithms proposed • • • • K-clique percolation Hierarchical clustering Girvan-Newman algorithm Modularity maximization (e.g., Louvain method) (diagram from Wikipedia) Modularity • A quantity that characterizes how good a given community structure is in dividing the network |Ein|-|Ein-R| Q = |E| • |Ein|: # of links connecting nodes that belong to the same community • |Ein-R|: Estimated |Ein| if links were random Community detection based on modularity • The Louvain method – Heuristic algorithm to construct communities that optimize modularity • Blondel et al. J. Stat. Mech. 2008 (10): P10008