这篇文章是对The structure and function of complex networks (Newman, 2003)的一个阅读梳理，仅作个人理解使用。在阅读时大量收集了来自互联网的各种资料，但当时并没有做好相关记录，如果涉及侵权请联系我删除。

---

1 The mind map of reading >>

This mind map is the structure of The structure and Function of Complex Networks.

2 The Goal of Learning The Network >>

Our ultimate goal in this field: to understand the behavior and function of the networked systems we see around us. If we can gain such understanding, it will give us new insight into a vast array of complex and previously poorly understood phenomena. >>

3 The structure and Function of Complex Networks >>

3.1 INTRODUCTION >>

3.1.1 >>

Types of networks

HyperGraph :One can also have hyperedges-edges that join more than two vertices together.

3.1.2 >>

Three aims of network theory: 1. To find properties 2. To understand properties 3. To predict behavior

3.2 NETWORKS IN THE REAL WORLD >>

3.2.1 Information networks >>

3.2.2 Technological networks >>

3.2.3 Social networks >>

3.2.4 Biological networks >>

3.3 PROPERTIES OF NETWORKS >>

3.3.1 The small-world effect 小世界效应>>

3.3.1.1 Average shortest path length >>

3.3.1.2 More than one component >>

3.3.1.3 >>

Small-word network:

Random network:

A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a small number of hops or steps.(Wiki )
大的簇系数和小的平均距离两个统计特征合在一起称为小世界效应。具有这种效应的网络就是小世界网络。 （真实网络几乎都具有小世界效应）

33.3.2 Transitivity or clustering 簇/聚类>>

3.3.2.1 >>

全局 针对整个网络:

局部 针对一个节点:

其实都是三元闭回路/三元开路
Local Average Clustering Coefficient 平均局部聚类系数:

3.3.2.1.1 如何找三元闭回路/三元开路>>

closed triplet ={1，(2,3)}，{2，(1,3)}，{3，(1,2)} all triplet = {1,(2,3)}，{2,(1,3)}，{3,(1,2)}，{3,(2,4)}，{3,(4,5)}，{3,(1,5)}，{3,(2,5)}，{3,(1,4)}
按照节点来找

3.3.3 Degree distributions >>

We define pk$p_k$ to be the fraction of vertices in the network that have degree k$k$.

3.3.3.1 Measuring this tail >>

3.3.3.1.1 >>

One is to constructed a histogram in which the bin sizes increase exponentially with degree. 即对数坐标系。

3.3.3.1.2 >>

An alternative way of presenting degree data is to make a plot of the cumulative distribution function

3.3.3.2 Scale-free networks 度分布呈现指数分布的网络>>

3.3.3.3 Maximum degree >>

一个网络中的最大度与节点数有以下关系，并附上证明：

3.3.4 Network resilience >>

网络抗破坏能力，鲁棒性

3.3.5 Mixing patterns >>

网络中各类顶点的连接度

3.3.5.1 >>

3.3.6 Degree correlations >>

连接度不同的顶点之间的联系

3.3.7 Community structure >>

社群结构

3.3.7.1 如何划分社群 >>

3.3.8 Network navigation >>

3.4 RANDOM GRAPHS >>

随机网络具有小的簇系数和小的平均距离（ER随机图的许多重要特性都是突然涌现的，也就是说给定边相连的概率P，要么几乎所有图都有某个性质，要么几乎所有图都不具有该性质）

3.4.1 Poisson random graphs >>

3.4.1.1 Take some number n of vertices and connect each pair (or not) with probability p$p$ (or1−p$1-p$).This defines the model that Erdős and Rényi called Gn,p$G_{n,p}$. 即ER模型 >>

3.4.2 Generalized random graphs >>

3.4.2.1 The configuration model >>

假设有n个节点，每个节点都被赋予了确定的度（表现为每个节点都有延伸出一定数量的桩，stub），随机将这些节点的桩连接起来，构成网络。

3.4.2.2 Directed graphs >>

3.4.2.3 Bipartite graphs >>

3.4.2.4 Degree correlations >>

3.4.2.4.1

They suggest that these anticorrelations are a simple result of the fact that the Internet graph has at most one edge between any vertex pair.

3.4.2.4.2

The configuration model, by contrast, allows double edges, and typical graphs usually have at least a few such edges, which would disqualify them from mem- bership in the ensemble of Maslov et al.
configuration model允许节点间复连接

3.5 EXPONENTIAL RANDOM GRAPHS AND MARKOV GRAPHS >>

3.6 THE SMALL-WORLD MODEL >>

小世界网络具有大的簇系数和小的平均距离 （小世界网络是在规则网络不改变原有边的基础上，以一个小的概率在原有网络上添加新边）

3.6.1 WS模型 >>

WS模型是基于两人的一个假设：小世界模型是介于规则网络和随机网络之间的网络。因此模型从一个完全的规则网络出发，以一定的概率将网络中的连接打乱重连。具体的构造如下： 首先从一个规则的网络开始。这个网络中的N个节点排成正多边形，每个节点都与离它最近的2K个节点相连。其中K是一个远小于N的正整数。 选择网络中的一个节点，从它开始（它自己是1号节点）将所有节点顺时针编号，再将每个节点连出的连接也按顺时针排序。然后，1号节点的第1条连接会有0<p<1$0<p<1$的概率被重连。重连方式如下：保持1号节点这一端不变，将连接的另一端随机换成网络里的另一个节点，但不能使得两个节点之间有多于1个连接。 重连之后，对2号、3号节点也做同样的事（如果这其中有连接已经有过重连的机会，就不再重复），直到绕完一圈为止。 再次从1号节点的第2条连接开始，重复第2个步骤和第3个步骤，直到绕完一圈为止。 再次从1号节点开始，重复第4个步骤，直到所有的连接都被执行过第2个步骤（重连的步骤）。 由于NK个连接里每个连接都恰好有一次重连的机会，所以这个过程最后总会结束。最后得到的网络称为WS模型网络。

3.6.2 Clustering coefficient >>

3.6.3 Average path length >>

3.6.4 特征图 >>

图中的横轴是p（使用对数坐标轴表示），纵轴是比值（介乎0与1之间）。蓝色曲线表示lavg(p)$l_{avg}(p)$与lavg(0)$l_{avg}(0)$之比，红色曲线表示C(p)$C(p)$与C(0)$C(0)$之比。从右图可以看到，蓝色曲线很快就逐渐下降到0.2以下，而红色曲线则直到超过p=10−1$p={10}^{-1}$后才开始有显著下降。当p=10−1$p={10}^{-1}$的时候，C(p)大概还有C(0)八成左右，但lavg(p)$l_{avg}(p)$只占lavg(0)$l_{avg}(0)$的不到百分之5了。所以对于很小的p，lavg⁡(p)可以很小，但C(p)可以很大。这正是小世界网络的特征。

3.6.5 Degree distribution >>

3.7 MODELS OF NETWORK GROWTH >>

3.7.1 Price’s model >>

可以看作有向的BA无标度模型（感觉BA模型更好理解）。

3.7.2 The model of Barabási and Albert >>

BA无标度模型
A dynamic model,”preferential attachment mechanism”

3.7.2.1 构造方法 >>

BA模型的具体构造为： 增长：从一个较小的网络G0$G_0$开始（这个网络有n0个节点，E0条边），逐步加入新的节点，每次加入一个。 连接：假设原来的网络已经有n个节点（s1,s2,⋯,sn$s_1,s_2,\cdots ,s_n$）。在某次新加入一个节点sn+1$s_n+1$时，从这个新节点向原有的n个节点连出m<n0$m<n_0$个连结。 优先连接：连接方式为优先考虑高度数的节点。对于某个原有节点si（1⩽i⩽n），将其在原网络中的度数记作di$d_i$，那么新节点与之相连的概率Pi$P_i$为： Pi=di∑ni=0dj$P_i=\frac{d_i}{\sum _{i=0}^n{d}_j}$这样，在经过t次之后，得到的新网络有n0+t$n_0+t$个节点，一共有E0+mt$E_0+mt$条边。

3.7.2.2 Degree Distribution >>

In the limit of large k this gives a power law degree distribution pk∼k−3$p_k\sim k^{-3}$

3.7.3 Generalizations of the Barabási-Albert model >>

3.7.4 Other growth models >>

3.7.5 Vertex copying models >>

注意一下该理论，在解释生物网络特别是带有循环复制的网络有有趣的想法。

3.7.5.1 模型内容 >>

In the general copying model, a growing network starts as a small initial graph and, at each time step, a new vertex is added with a given number k of new outgoing edges. As a result of a stochastic selection, the neighbors of the new vertex are either chosen randomly among the existing vertices, or one existing vertex is randomly selected and k of its neighbors are ‘copied’ as heads of the new edges.(Wiki)

3.8 PROCESSES TAKING PLACE ON NETWORKS >>

3.8.1 Percolation theory and network resilience >>

3.8.2 Epidemiological processes >>

3.8.2.1 The SIR model >>

3.8.2.1.1 SIR模型的三个参数 >>

Blue=Susceptible, Green=Infected, and Red=Recovered

3.8.2.2 The SIS model >>

3.8.2.2.1 >>

Blue=Susceptible, Green=Infected, and Red=Recovered. Susceptibles and infected get equilibrated.

3.8.3 Search on networks >>

3.8.3.2 Guided network search >>

3.8.3.3 Network navigation >>

3.8.4 Phase transitions on networks >>

3.8.5 Other processes on networks >>

3.9 SUMMARY AND DIRECTIONS FOR FUTURE RESEARCH >>

---

参考资料：
复杂网络综述
Clustering coefficient的定义
Compartmental models in epidemiology
Small-world network
无尺度网络
Barabási–Albert model
Network Analysis. Lecture 3. Random graphs.
Barabasilab_course