Complex networks A. Barrat, LPT, Université Paris-Sud, France
Complex networks: examples
Complex networks: examples
Small-world networks
Scale-free networks: evidences, modeling, tools for characterization
Consequences of SF structure
Perspectives: weighted complex networks
Examples of complex networks
Internet
WWW
Transport networks
Protein interaction networks
Food webs
Social networks
...
Social networks: Milgram’s experiment
Asymptotic behavior
In-between: Small-world networks
Size-dependence
Is that all we need ?
Is that all we need ?
Tools for characterizing the various models
Connectivity distribution P(k)
=>Homogeneous vs. Scale-free
Clustering
Assortativity
...
Topological correlations: clustering
aij: Adjacency matrix
Topological correlations: assortativity
Assortativity
Assortative behaviour: growing knn(k)
Example: social networks
Large sites are connected with large sites
Disassortative behaviour: decreasing knn(k)
Example: internet
Large sites connected with small sites, hierarchical structure
Consequences of the topological heterogeneity
Robustness and vulnerability
Propagation of epidemics
Other attack strategies
Most connected nodes
Nodes with largest betweenness
Removal of links linked to nodes with large k
Removal of links with largest betweenness
Cascades
...
Betweenness
measures the “centrality” of a node i:
for each pair of nodes (l,m) in the graph, there are
lm shortest paths between l and m
ilm shortest paths going through i
bi is the sum of ilm / lm over all pairs (l,m)
Other attack strategies
Most connected nodes
Nodes with largest betweenness
Removal of links linked to nodes with large k
Removal of links with largest betweenness
Cascades
...
What about computer viruses?
Very long average lifetime (years!) compared to the time scale of the antivirus
Small prevalence in the endemic case
SIS model on SF networks
SIS= Susceptible – Infected – Susceptible
Mean-Field usual approximation: all nodes are “equivalent” (same connectivity) => existence of an epidemic threshold 1/ for the order parameter density of infected nodes)
Scale-free structure => necessary to take into account the strong heterogeneity of connectivities => k=density of infected nodes of connectivity k