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

2022
Views:

494

Pages:

9
Author:

Carloppiv5fr

Measuring Topological Properties of Networks (1): Macroscopic Properties Network density • The ratio of # of actual links and # of possible links – For an undirected graph: d = |E| / ( |V| (|V| - 1) / 2 ) – For a directed graph: d = |E| / ( |V| (|V| - 1) ) Characteristic path length • In graph theory: Maximum of shortest path lengths between pairs of nodes (a.k.a. network diameter) • In complex network science: Average shortest path lengths • Characterizes how large the world being modeled is – A small length implies that the network is well connected globally Clustering coefficient • For each node: – Let n be the number of its neighbor nodes – Let m be the number of links among the k neighbors – Calculate c = m / (n choose 2) Then C = (the average of c) • C indicates the average probability for two of one’s friends to be friends too – A large C implies that the network is well connected locally to form a cluster Degree distribution P(k) = Prob. (or #) of nodes with degree k • Gives a rough profile of how the connectivity is distributed within the network Sk P(k) = 1 (or total # of nodes) Power law degree distribution • P(k) ~ k-g A few well-connected nodes, a lot of poorly connected nodes log P(k) P(k) log k Scale-free network k Linear in log-log plot -> No characteristic scale (Scale-free networks) How it appears Random Scale-free Degree Distributions of Real-World Complex Networks Actors WWW Power grid Degree distribution of FB P(k) CCDF