复杂网络理论及其应用课件(2011-4-13)

Complex network and its applications

高忠科

Apr 13, 2011

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

关于复杂性

我们所关心的问题：

大量个体（更典型的是具有适应性的主体）所组成的复杂系统，在没有中心控制、非完全信息、仅仅存在局域相互作用的条件下，通过个体之间的非线性相互作用，可以在宏观层次上涌现出一定的结构和功能。

相互作用与复杂性

晶格全局相互作用 Internet

扩散

平均场

什么是复杂网络？

复杂网络是对复杂系统的抽象和描述方式，任何包含大量组成单元（或子系统）的复杂系统，当把构成单元抽象成节点、单元之间的相互关系抽象为边时，都可以当作复杂网络来研究。复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础。

什么是复杂网络？

Watts DJ and Strogatz SH, Nature 393, 440 (1998) Citation: 4911 (Small-world network)

Barabási AL and Albert R, Science 286, 509 (1999) Citation: 5474 （Scale-free network）

复杂网络为研究复杂系统提供了一个全新的视角，对理解真实系统的复杂行为起着重要的作用。复杂网络研究的兴起，广泛应用于社会学，物理统计学，经济学，控制学，工程学，生物医学等多个跨学科研究领域。

Emergence of a networked life

Communities Atom

Organisms Molecule Tissue Cell

Organs

为什么研究复杂网络？

复杂系统不能够用分析的方法去研究，必须考虑个体之间的关联和作用；理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始；网络拓扑结构的信息是构建系统模型、研究系统性质和功能的基础。

为什么研究复杂网络？

复杂网络是构成复杂系统的基本框架( backbone )，每一个复杂系统都可以看作是单元或个体之间的相互作用网络；

复杂网络在刻画复杂性方面的重要性是由于结构和功能之间是相互影响的。

Examples of Complex Networks

The worldwide air transportation network: a real socio-economic network

Guimera, Mossa, Turtschi, Amaral, PNAS (2005)

The protein interactome of yeast: a real biochemical network

Jeong, Mason, Barabasi, Oltvai, Nature (2001)

生命金字塔

不同领域的复杂网络

1 1

社会网：演员合作网，友谊网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因调控网络信息网络：WWW，专利使用，论文引用，计算机共享技术网络：电力网，Internet，电话线路网交通运输网：航线网，铁路网，自然河流网时

间序列信号复杂网络：流型复杂网络，脑功能网络，金融网络等

1 1 1 1

网络研究的历史

1 1736，欧拉：哥尼斯堡七桥

1 1950，Erdos,

Renyi: 随机图论 Barabasi: 小世界和无标度网络

1 1998，Strogatz,

为什么现在才开始研究复杂网络？

1 计算机技术的发展：

h 使我们拥有各种网络的数据库，并有可能对大规模的网络

进行实证研究

1 普适性的发现：

h 许多实际网络具有相同的定性性质 h 且已有的理论不能描述和解释

1 理论研究的发展

h 小世界网络

(Small World Network), 无标度网络 (Scale-free

Network)

h 统计物理学的研究手段

复杂网络研究所关心的问题

1 如何定量刻画复杂网络？

h 网络结构的描述及其性质

1 网络是如何发展成现在这种结构的？

h 网络演化模型

1 网络特定结构的后果是什么？

h 网络结构的鲁棒性 h 网络上的动力学行为和过程

How to investigate Complex Networks?

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

Describing a network formally

nodes and E edges, E ≤ N(N-1)/2

1 where

= 7, E = 9

Note: In graph theory language this graph is of order 7 and size 9.

Directed networks

More edges: E ≤ N(N-1)

Much more complex topology.

Adjacency matrix

The most convenient way of describing a network is the adjacency matrix aij.

A link between node i to node j is recorded by a ‘1’ in the ith row and the jth column.

Adjacency matrix

Undirected networks have a symmetric adjacency matrix aij.

Directed networks in general have asymmetric aij.

Weighted networks

In a weighted network a real number is attached to each edge, so that we obtain a real adjacency matrix, usually denoted as wij.

Degree

In an undirected network the degree ki of a node i is the number of nodes i is connected to: ki = Σj aij = Σj aji

Here k1 = 2, k2 = 4, k3 = 1, k4 = 3 and k5 = 2.

In-degree and out-degree

In a directed network the in-degree ki (in) of a node i is the number of directed edges pointing to node i: ki (in) = Σj aji while the out-degree ki (out) of a node i is the number of directed edges pointing from node i: ki (out) = Σj aij

In-degree and out-degree

Thus, in a directed network, nodes can be highly connected, yet also isolated (e.g. in terms of sending or receiving information.)

In-degree and out-degree Citations

The network of scientific citations provide examples illustrating two extremes:

High in-degree and low out-degree: much-cited research article

Low in-degree and high out-degree: Book or review article

Strength

In a weighted, undirected network the strength is the sum of the weights for the edges connecting to a node: si = Σj wij = Σj wji

Hence s1 = 4, s2 = 18, s3 = 2, s4 = 13 and s5 = 15.

Shortest path length

The distance between two nod

es i and j is the shortest path connecting the two nodes.

i j

dij = 4

i j

Average shortest path length：

Diameter

The diameter of a network is the largest distance in the network - in other words it is the maximum shortest path connecting any two nodes.

D=2

D=1

Note: Fully connected networks (like the one on the right) have diameter D = 1.

Clustering coefficient

The clustering coefficient measures how densely connected the neighborhood of a node is. It does this by counting the number of triangles of which a given node i is a part of, and dividing this value by the number of edge pairs.

Often the clustering coefficient is averaged over the entire network:

Where N is the number of nodes.

Betweenness

The communication of two non-adjacent nodes, say j and k, depends on the nodes belonging to the paths connecting j and k. Consequently, a measure of the relevance of a given node can be obtained by counting the number of geodesics going through it, and defining the so-called node betweenness, defined as:

where njk is the number of shortest paths connecting j and k, while njk(i) is the number of shortest paths connectingj and k and passing through i. Standard measures of node centrality

Assortativity

Assortativity describes the correlation between the degree of a node and the degree of its neighbors. Networks in which highly connected nodes are linked to other nodes with a high degree are termed assortative. Such networks include social networks.

Networks in which highly connected nodes are only linked to nodes with a low degree are termed disassortative. Such networks include the World Wide Web and biological networks.

Assortativity Coefficient

One way of measuring assortativity is to determine the Pearson correlation coefficient between the degrees of pairs of connected nodes. This is termed the associativity coefficient r: r = (1/σq) Σjk jk (ejk - qjqk) and lies between -1 (disassortative) and 1 (assortative). Some values for real networks: Physics coauthorship: 0.363 Company directors: 0.276 Internet: Marine food web: -0.189 -0.247

Degree distribution

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

规则网络

1 1 1 1 1

规则网络是指平移对称性晶格,任何一个格点的近邻数目都相同。各个节点的具有相同的度值如图为最近邻耦合网络：每个节点都与它左右的K/2个节点相连。对大的N, K, 有：聚集系数C~3/4, 平均路径长度L~无穷大一般地，规则网络具有大的聚集系数和大的最短平均距离

随机网络

ER随机图模型：顶点的度值服从 Poisson distribution，也称 Poisson随机图

1 1 1 1

平均度：k~p*N 平均路径长度L~ln(N)/ln(k) 聚集系数: C=p

一般地，随机网络具有小的聚集系数和小的最短平均距离。

The Small World Experim

ent

斯坦利•米尔格伦(Stanley Milgram)在1967年通过一斯坦利• 米尔格伦(Stanley Milgram) 1967年通过一些实验后得出结论：中间的联系人平均只需要5个。些实验后得出结论：中间的联系人平均只需要5 他把这个结论称为”六度分离” 。他把这个结论称为” 六度分离” 六度分离: 平均只要通过5个人，你就能与世界任何六度分离: 平均只要通过5 一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程明了我们世界的” 大小” 度。

The Small World Experiment

D. watts

2001年开始, 18名目标对象, 166个国家共 6万多志愿者, 平均转发5-7次

The Small World Experiment

Path Length

Clustering Coefficient

Small World模型

是否存在一个同时具有高的集聚程度，小的最短路径网络呢? 对于传染病模型，平均集聚程度对应于传播的广度，平均最短距离代表的是传播的深度。因此,如果实际网络同时存在宽的广度和大的深度的话，在这样的网络上的传染病传播显然将大大高于规则网络与随机网络。

1998年Watts和Strogatz 为我们找到了这样的网络模型—Small World 网络（发表在Nature上）。现在常称为：WS model

Small World模型

方法：Watts和Strogatz 发现,只需要在规则网络上稍作随机改动就可以同时具备以上两个性质。改动的方法是，对于规则网络的每一个顶点的所有边,以概率p 断开一个端点，并重新连接,连接的新的端点从网络中的其他顶点里随机选择，如果所选的顶点已经与此顶点相连，则再随机选择别的顶点来重连。当p = 0 时就是规则网络， p = 1 则为随机网络,对于0

Small World模型

Scale-Free 网络模型

1 1 1

1999年，Barabási 和Albert给出了构造无标度网络的演化模型。形成机制：生长和择优连接取初始m0个顶点任意连接或完全连接。每一步在原网络G( t - 1) 的基础上加上一个新的顶点，同时加上从此顶点出发的m 条边，形成新的网络 G ( t ) 。其中对任意一个已存在节点i，它与新顶点建立连接概率为：

pi = ki / Σj kj

随机选取。重复以上新加点的过程足够多步所形成的网络的各顶点的度满足幂律分布P(k) = k -γ 。而且指数γ = 3 与模型的参数m0 , m 无关。进一步的数值模拟表明，当m 取某一范围内的随机数时，指数也不变。现在常称为： BA Model

1 1

Scale-Free 网络模型

BA Model

P(k) ~k-3

A.-L.Barabási, R. Albert, Science 286, 509 (1999)

Scale-Free 网络模

型

Scale-Free 网络模型

World Wide Web

Nodes: WWW documents Links: URL links 800 million documents (S. Lawrence, 1999)

INTERNET BACKBONE

Nodes: computers, routers Links: physical lines

ACTOR CONNECTIVITIES

Nodes: actors Links: cast jointly

P(k) ~k-γ γ=2.3 N = 212,250 actors 〈k〉 = 28.78

SCIENCE CITATION INDEX

Nodes: papers Links: citations

SCIENCE COAUTHORSHIP

Nodes: scientist (authors) Links: write paper together

1736 PRL papers (1988)

(Newman, 2000, H. Jeong et al 2001)

Metabolic network

Archaea 古生菌

Bacteria 细菌

Eukaryotes 真核生物

Organisms from all three domains of life are scale-free networks!

H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, and A.L. Barabasi, Nature, 407 651 (2000)

Internet

无标度网络鲁棒性

Resilience of Networks

We consider the resilience of the network to the removal of its nodes (site percolation) or edges (bond percolation). As nodes (or edges) are removed from the network, the average path length will increase. Ultimately, the giant component will disintegrate. Networks vary according to their level of resilience to node (or edge) removal.

无标度网络鲁棒性

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

复杂网络社团结构及其探寻算法 We need a “cartography” of complex networks

1 Community One divides the system into “regions”

1 Roles One highlights important players

Political Blogs

What is a Community

Groups of nodes within which connections are dense, but between which connections are sparser

Twitter Network

Facebook Network

复杂网络社团结构及其探寻算法

Santa Fe研究所的科学家合作网

Girvan-Newman (GN) algorithm

A B M. Girvan and M. E. J. Newman, PNAS 99: 7821 (2002) M. E. J. Newman and M. Girvan, Phys. Rev. E 69: 026113 (2004)

The few edges that lie between communities can be thought of as forming “bottlenecks” between the communities. Betweenness and edge betweenness : Edge removal : After calculating the betweenness of all edges in the network, remove the one with highest betweenness. Recalculate after edge removal and repeat it until the modularity Q is maximum. Time complexity O(m2n)

复杂网络社团结构及其探寻算法

Heuristic methods to identify modules in complex networks: Girvan-Newman algorithm

A B D

1 1

Identify the most central edge in the network Remove the most central edge in the network Iterate the process Edge Betweenness

F H I

Girvan & Newman, PNAS (2002)

Modularity

Let eij be the fraction of edges in the network that connect nodes in community i to those in community j, and let

ai = ∑ j eij

. Then

∑ (e

− ai )

is the fraction of edges that fall within commu

nities, minus the expected value of the same quantity if edges fall at random without regard for the community structure. If a particular division gives no more within-community edges than would be expected by random chance we will get Q=0. Values other than 0 indicate deviations from randomness, and in practice values greater than about 0.3 appear to indicate significant community structure

复杂网络社团结构及其探寻算法

Modularity

Q = ∑ eii − ∑ eij eki = Tr e − e 2

i ijk

The community tree of a real organization

The Girvan-Newman algorithm for module detection is remarkably effective

Newman fast algorithm

Modularity

M. E. J. Newman, Phys. Rev. E 69: 066133 (2004) Maximize Q by greedy algorithm !

∑e

− ∑ eij e ki = Tr e − e 2

ijk

1. Separate each node solely into n community.

⎧1/ 2m eij = ⎨ ⎩ 0

aij = ki / 2m

2. Calculate the increase of Q for all possible community pairs.

ΔQ = eij + e ji − 2ai a j = 2(eij − ai a j )

3. Choose the mergence of the greatest increase in Q. 4. Repeat 2 & 3 until the modularity Q reaches the maximal value. Agglomerative hierarchical clustering method!

How does network cartography help us understand the metabolism?

Metabolic network of E. coli

Extracting information from complex networks

Protein interactions in fruit fly Giot et al., Science (2003)

Genetic interaction network

As we already knew, geo-political factors determine the modular structure of the air transportation network

Guimera, Mossa Turtschi, Amaral, PNAS (2005)

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

复杂网络的自相似性（分形）

盒记数法：计算一个集合图形维数的基本思想是用边长为 lB 的盒子来覆盖该图形，并统计完全覆盖该图形所需要的最少的盒子数 NB(lB). 这里的盒子在一维情形下为线段，二维下为正方形，三维下为立方体， lB 称为盒子尺寸. 分形维数为

dB ≈ −

ln N B (lB ) ln(lB )

N B (lB ) ≈ lB − d B

复杂网络的自相似性（分形）

在复杂网络研究中,Song等人通过把盒式计数方法推广用于复杂网络,指出许多复杂网络也存在类似于分数维的自相似指数,从而也具有某种内在的自相似性。 Song等人对用于覆盖复杂网络的尺寸为 lB 的盒子的规定为:盒子中任意两个节点间的距离都小于 lB, NB 是覆盖网络的最少的盒子数。

Song等人进一步通过采用重整化过程,揭示出自相似性和无标度的度分布在网络的所有粗粒化阶段都成立。

Song C, Havlin S, Makse H A, Self-similarity of complex network, Nature, 2005, 433:392

复杂网络的自相似性（分形）

Song C, Havlin S, Makse H A, Self-similarity of complex network, Nature, 2005, 433:392

复杂网络的自相似性（分形）

重整化

后

Song C, Havlin S, Makse H A, Self-similarity of complex network, Nature, 2005, 433:392

复杂网络的自相似性（分形）

Song C, Havlin S, Makse H A, Self-similarity of complex network, Nature, 2005, 433:392

复杂网络的自相似性（分形）

一般网络的粗粒化过程是指把网络中的具有某种共同性质的节点集合,用单个新节点表示,这样就可以得到一个具有较少节点的新的网络。值得指出，对一个网络存在多种粗粒化方法，在一种粗粒化过程下具有自相似的一个网络在另一种粗粒化过程下却可能具有非自相似性。

疾病传播动力学：SI 模型

Infectious Susceptible contact

易受感染者传染者

接触数目

∝ I×S

i(t):群体中t时刻处于I态的密度 s(t):群体中t时刻处于S态的密度

λ : 传染概率

⎧ d s (t ) ⎪ d t = − λ i (t ) s (t ) ⎪ ⎪ d i (t ) = λ i (t ) s (t ) ⎨ ⎪ dt ⎪ i (t ) + s (t ) = 1 ⎪ ⎩

疾病传播动力学：SIS 模型

S (i ) + I ( j ) → I (i ) + I ( j ) I (i ) → S (i )

i(t):群体中t时刻处于I态的密度 s(t):群体中t时刻处于S态的密度

u : 治愈概率

: 传染概率

ds (t ) = − λ i (t ) s (t ) + ui (t ) dt di (t ) = λ i (t ) s ( t ) − ui ( t ) dt i (t ) + s (t ) = 1

存在一个阈值

λc λ > λc

时定态解 i (T)>0 T 为达到稳定态的时间

疾病传播动力学：SIR 模型

S (i ) + I ( j ) → I (i ) + I ( j ) I (i ) → R(i )

i(t):群体中t时刻处于I态的密度 s(t):群体中t时刻处于S态的密度 r(t):群体中t时刻处于R态的密度

u : 免疫概率

λ : 传染概率

⎧ d s (t ) ⎪ d t = − λ i (t ) s (t ) ⎪ ⎪ d i (t ) = λ i (t ) s (t ) − u i (t ) ⎪ ⎨ dt ⎪ d r (t ) = u i (t ) ⎪ ⎪ dt ⎪ i (t ) + s (t ) = 1 ⎩

λ λc 传染爆发并变为全局性的

疾病传播动力学：规则-复杂网络（拓扑机构）

SIS Model

疾病传播动力学：规则-复杂网络（拓扑机构）

SIR Model

疾病传播动力学：小世界网络上的传播

（SIS Model）被感染节点的密度随时间的演化满足如下方程

d ρ (t ) = − ρ ( t ) + λ k ρ ( t ) (1 − ρ ( t ) ) dt

右边第一项表示感染节点以单位速率减少；第二项表示新感染的节点数目正比于传染率λ 、从每个节点出发的连线数、及给定连线指向易感染人群的概率 ρ ( t ) (1 − ρ ( t ) ) 得出流行病传播的阈值为

λc = k

−1

ρ = 0, when λ

SIR Model 结论一样

疾病传播动力学：无标度网络上的传播

（SIS Model）被感染节点的密度随时间的演化满足如下方程

d ρk ( t ) = − ρ k ( t ) + λ k ⎡1 − ρ k ( t ) ⎤ ∑ P ( k ' | k ) ρ k ' ( t ) ⎣ ⎦ ' dt k

右边第一项描述由于单位恢复率导致的感染群体的湮灭；第二项为产生项，正比于感

染人群的密度 1 − ρ k ( t ) 乘以传播率 λ 、邻居数 k 、及任意邻居被感染的概率，后者为从一个度为 k 的节点连向度为任意 k ' 的节点的联合概率 P ( k ' | k ) ρ k ( t ) 的平均。

得出流行病传播的阈值为

SIR Model 结论一样

k2 = ∞

P(k ) ~ k −γ , γ ≤ 3

λc → 0

疾病传播动力学：规则-复杂网络（拓扑机构）

气液两相流流型复杂网络

两相流动态实验

天津大学多相流实验室

利用自行研制的纵向多极阵列电导式传感器采集两相流动态波动信号

气液两相流流型复杂网络

泡状流

泡状-段塞过渡流型

0 .0 4 0 .0 0 -0 .0 4 0 .3 0 .0

段塞流

U s w = 0 .1 8 m /s ,U s g= 0 .0 1 m /s

段塞-混状过渡流型

B u b b le f lo w

混状流

U s w = 0 .1 8 m /s ,U s g = 0 .0 4 m /s

B u b b le -s lu g tr a n s itio n a l f lo w

Signals (volt)

-0 .3 0 .6 0 .0 -0 .6 0 .8 0 .0 -0 .8 0 .8 0 .0 -0 .8 0 2 4 6 8 10 12 14 16 18 20

U sw = 0 .1 8 m /s,U sg = 0 .1 2 m /s

S lu g f lo w

U sw = 0 .1 8 m /s,U sg = 0 .3 5 m /s

S lu g - c h u r n tra n s itio n a l f lo w

U sw = 0 .1 8 m /s,U sg= 0 .6 1 m /s

C h u r n f lo w

Time (s)

五种典型气液两相流流型的电导波动信号

气液两相流流型复杂网络

流型复杂网络

基于实验测量信号，以不同的气液配比流动工况为节点，在此基础上提取每个流动工况下与流型发展转化密切相关的电导波动信号特征量，并以各个流动工况间特征量的相关性强度为边，从而构建流型复杂网络。

气液两相流流型复杂网络

时频域特征提取

时域特征提取：最大（小）值、均值、标准差、非对称系数、峭度系数。频域特征提取：线性预估器四个系数

C-C算法确定最佳延迟时间

C ( m, N , r , τ ) =

2 ∑ θ r − Xi − X j M ( M − 1) 1≤i

{

}

序列长度N

1000 2000 5000 6000 9000 10000

1 S (m, N , r , 2) = {[C1 (m, N / 2, r , 2) − C1m (1, N / 2, r , 2)] + (C2 (m, N / 2, r , 2) − C2 m (1, N / 2, r , 2))} 2

S (m, N , r , t ) =

ΔS (m, t ) = max {S (m, rj , t , N )} − min {S (m, rj , t , N )}

1 5 Δ S (t ) = ∑ Δ S ( m , t ) 4 m=2

1 t ∑ {Cs (m, N / t , r , t ) − Csm (1, N / t , r , t )} t s =1

ΔS(t)

0.20

C-C Method

0.16 0.12 0.08 0.04 0.00 0 20 40 60

最佳延迟时间应该是Δ S (t ) 首次到达最小值所对应的时间 τ d 。

t =

τd τs

100 120 140 160

气液两相流流型复杂网络

Gao Z K and Jin N D, Phys. Rev. E 79: 066303 (2009)

十个时域特征量相关性因子

Cij =

∑ ⎡T (k ) − ⎣

k =1 i

⎤ ⎣ Ti ⎦ ⋅ ⎡ Tj (k ) − Tj ⎤ ⎦

∑ ⎡ T (k ) − ⎣

k =1 i

Ti ⎦ ⋅ ⎤

∑ ⎡T (k ) − ⎣

k =1 j

Tj ⎤ ⎦

0.35

流型复杂网络邻近矩阵Dij及相关性阈值判据rc

0.30 0.25 0.20 0.15 0.80

τ=9 Δt τ=7 Δt τ=5 Δt τ=17 Δt τ=25 Δt

rc=0.98

⎧1, ⎪ Dij = ⎨ ⎪0, ⎩

( Cij ≥ rc ) ( Cij

0.85

0.90

0.95

1.00

气液两相流流型复杂网络

1 1

基于K-means聚类的社团探寻算法基于数据场理论的社团探寻算法

实际网络-Zachary网络社团结构图社团结构不明显的网络--Newman等人在提出的拥有4个社团且其大小均为32的算例网络结构

气液两相流流型复杂网络

Gao Z K and Jin N D, Phys. Rev. E 79: 066303 (2009)

流型复杂网络社团结构

发现了网络中对应于泡状流、段塞流及混状流的三个社团和对应于两种过渡流型的社团间联系紧密节点，从而实现了垂直气液两相流流型识别。

气液两相流流型复杂网络

两相流流型复杂网络构建 1.以延迟嵌入方法对信号进行非线性预处理。 2.提取不同流动工况下信号的10个特征量。 3.以流动工况为节点，基于模块度以各个流动工况间特征量的相关性强度为边构建两相流流型复杂网络。

流型复杂网络社团结构探寻采用基于K-means聚类的网络社团探寻算法分析油水两相流流型复杂网络，寻找网络中联系紧密的节点族。

流型复杂网络社团结构图绘制采用网络可视化软件UCINET和NETDRAW绘制所探寻到的流型复杂网络社团结构图。

垂直气液/倾斜油水两相流流型定义采用安装在实验管道上的高速动态摄像仪/微电导探针阵列传感器测量信号特征对垂直气液/倾斜油水两相流流型进行实验确定。

社团结构与实验流型对比验证高速动态摄像仪/微电导探针阵列传感器信号定义的实验流型与所探寻得到的社团结构进行对比验证，找出不同流型对应社团结构，实现垂直气液/倾斜油水两相流流型识别。

基于流型复杂网络社团结构的两相流流型辨识流程图

Complex network and its applications

高忠科

Apr 13, 2011

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

关于复杂性

我们所关心的问题：

相互作用与复杂性

晶格全局相互作用 Internet

扩散

平均场

什么是复杂网络？

Watts DJ and Strogatz SH, Nature 393, 440 (1998) Citation: 4911 (Small-world network)

Barabási AL and Albert R, Science 286, 509 (1999) Citation: 5474 （Scale-free network）

Emergence of a networked life

Communities Atom

Organisms Molecule Tissue Cell

Organs

为什么研究复杂网络？

复杂网络是构成复杂系统的基本框架( backbone )，每一个复杂系统都可以看作是单元或个体之间的相互作用网络；

复杂网络在刻画复杂性方面的重要性是由于结构和功能之间是相互影响的。

Examples of Complex Networks

The worldwide air transportation network: a real socio-economic network

Guimera, Mossa, Turtschi, Amaral, PNAS (2005)

The protein interactome of yeast: a real biochemical network

Jeong, Mason, Barabasi, Oltvai, Nature (2001)

生命金字塔

不同领域的复杂网络

1 1

间序列信号复杂网络：流型复杂网络，脑功能网络，金融网络等

1 1 1 1

网络研究的历史

1 1736，欧拉：哥尼斯堡七桥

1 1950，Erdos,

Renyi: 随机图论 Barabasi: 小世界和无标度网络

1 1998，Strogatz,

为什么现在才开始研究复杂网络？

1 计算机技术的发展：

h 使我们拥有各种网络的数据库，并有可能对大规模的网络

进行实证研究

1 普适性的发现：

h 许多实际网络具有相同的定性性质 h 且已有的理论不能描述和解释

1 理论研究的发展

h 小世界网络

(Small World Network), 无标度网络 (Scale-free

Network)

h 统计物理学的研究手段

复杂网络研究所关心的问题

1 如何定量刻画复杂网络？

h 网络结构的描述及其性质

1 网络是如何发展成现在这种结构的？

h 网络演化模型

1 网络特定结构的后果是什么？

h 网络结构的鲁棒性 h 网络上的动力学行为和过程

How to investigate Complex Networks?

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

Describing a network formally

nodes and E edges, E ≤ N(N-1)/2

1 where

= 7, E = 9

Note: In graph theory language this graph is of order 7 and size 9.

Directed networks

More edges: E ≤ N(N-1)

Much more complex topology.

Adjacency matrix

The most convenient way of describing a network is the adjacency matrix aij.

A link between node i to node j is recorded by a ‘1’ in the ith row and the jth column.

Adjacency matrix

Undirected networks have a symmetric adjacency matrix aij.

Directed networks in general have asymmetric aij.

Weighted networks

In a weighted network a real number is attached to each edge, so that we obtain a real adjacency matrix, usually denoted as wij.

Degree

In an undirected network the degree ki of a node i is the number of nodes i is connected to: ki = Σj aij = Σj aji

Here k1 = 2, k2 = 4, k3 = 1, k4 = 3 and k5 = 2.

In-degree and out-degree

Thus, in a directed network, nodes can be highly connected, yet also isolated (e.g. in terms of sending or receiving information.)

In-degree and out-degree Citations

The network of scientific citations provide examples illustrating two extremes:

High in-degree and low out-degree: much-cited research article

Low in-degree and high out-degree: Book or review article

Strength

In a weighted, undirected network the strength is the sum of the weights for the edges connecting to a node: si = Σj wij = Σj wji

Hence s1 = 4, s2 = 18, s3 = 2, s4 = 13 and s5 = 15.

Shortest path length

The distance between two nod

es i and j is the shortest path connecting the two nodes.

i j

dij = 4

i j

Average shortest path length：

Diameter

The diameter of a network is the largest distance in the network - in other words it is the maximum shortest path connecting any two nodes.

D=2

D=1

Note: Fully connected networks (like the one on the right) have diameter D = 1.

Clustering coefficient

Often the clustering coefficient is averaged over the entire network:

Where N is the number of nodes.

Betweenness

where njk is the number of shortest paths connecting j and k, while njk(i) is the number of shortest paths connectingj and k and passing through i. Standard measures of node centrality

Assortativity

Networks in which highly connected nodes are only linked to nodes with a low degree are termed disassortative. Such networks include the World Wide Web and biological networks.

Assortativity Coefficient

Degree distribution

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

规则网络

1 1 1 1 1

随机网络

ER随机图模型：顶点的度值服从 Poisson distribution，也称 Poisson随机图

1 1 1 1

平均度：k~p*N 平均路径长度L~ln(N)/ln(k) 聚集系数: C=p

一般地，随机网络具有小的聚集系数和小的最短平均距离。

The Small World Experim

ent

The Small World Experiment

D. watts

2001年开始, 18名目标对象, 166个国家共 6万多志愿者, 平均转发5-7次

The Small World Experiment

Path Length

Clustering Coefficient

Small World模型

1998年Watts和Strogatz 为我们找到了这样的网络模型—Small World 网络（发表在Nature上）。现在常称为：WS model

Small World模型

Scale-Free 网络模型

1 1 1

pi = ki / Σj kj

1 1

Scale-Free 网络模型

BA Model

P(k) ~k-3

A.-L.Barabási, R. Albert, Science 286, 509 (1999)

Scale-Free 网络模

型

Scale-Free 网络模型

World Wide Web

Nodes: WWW documents Links: URL links 800 million documents (S. Lawrence, 1999)

INTERNET BACKBONE

Nodes: computers, routers Links: physical lines

ACTOR CONNECTIVITIES

Nodes: actors Links: cast jointly

P(k) ~k-γ γ=2.3 N = 212,250 actors 〈k〉 = 28.78

SCIENCE CITATION INDEX

Nodes: papers Links: citations

SCIENCE COAUTHORSHIP

Nodes: scientist (authors) Links: write paper together

1736 PRL papers (1988)

(Newman, 2000, H. Jeong et al 2001)

Metabolic network

Archaea 古生菌

Bacteria 细菌

Eukaryotes 真核生物

Organisms from all three domains of life are scale-free networks!

H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, and A.L. Barabasi, Nature, 407 651 (2000)

Internet

无标度网络鲁棒性

Resilience of Networks

无标度网络鲁棒性

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

复杂网络社团结构及其探寻算法 We need a “cartography” of complex networks

1 Community One divides the system into “regions”

1 Roles One highlights important players

Political Blogs

What is a Community

Groups of nodes within which connections are dense, but between which connections are sparser

Twitter Network

Facebook Network

复杂网络社团结构及其探寻算法

Santa Fe研究所的科学家合作网

Girvan-Newman (GN) algorithm

A B M. Girvan and M. E. J. Newman, PNAS 99: 7821 (2002) M. E. J. Newman and M. Girvan, Phys. Rev. E 69: 026113 (2004)

复杂网络社团结构及其探寻算法

Heuristic methods to identify modules in complex networks: Girvan-Newman algorithm

A B D

1 1

Identify the most central edge in the network Remove the most central edge in the network Iterate the process Edge Betweenness

F H I

Girvan & Newman, PNAS (2002)

Modularity

Let eij be the fraction of edges in the network that connect nodes in community i to those in community j, and let

ai = ∑ j eij

. Then

∑ (e

− ai )

is the fraction of edges that fall within commu

复杂网络社团结构及其探寻算法

Modularity

Q = ∑ eii − ∑ eij eki = Tr e − e 2

i ijk

The community tree of a real organization

The Girvan-Newman algorithm for module detection is remarkably effective

Newman fast algorithm

Modularity

M. E. J. Newman, Phys. Rev. E 69: 066133 (2004) Maximize Q by greedy algorithm !

∑e

− ∑ eij e ki = Tr e − e 2

ijk

1. Separate each node solely into n community.

⎧1/ 2m eij = ⎨ ⎩ 0

aij = ki / 2m

2. Calculate the increase of Q for all possible community pairs.

ΔQ = eij + e ji − 2ai a j = 2(eij − ai a j )

3. Choose the mergence of the greatest increase in Q. 4. Repeat 2 & 3 until the modularity Q reaches the maximal value. Agglomerative hierarchical clustering method!

How does network cartography help us understand the metabolism?

Metabolic network of E. coli

Extracting information from complex networks

Protein interactions in fruit fly Giot et al., Science (2003)

Genetic interaction network

As we already knew, geo-political factors determine the modular structure of the air transportation network

Guimera, Mossa Turtschi, Amaral, PNAS (2005)

Outline

1 2 3 4

复杂系统与复杂网络

描述复杂网络基本统计量

小世界和无标度网络模型

社团结构及其探寻算法

复杂网络应用举例

复杂网络的自相似性（分形）

dB ≈ −

ln N B (lB ) ln(lB )

N B (lB ) ≈ lB − d B

复杂网络的自相似性（分形）

Song等人进一步通过采用重整化过程,揭示出自相似性和无标度的度分布在网络的所有粗粒化阶段都成立。

Song C, Havlin S, Makse H A, Self-similarity of complex network, Nature, 2005, 433:392

复杂网络的自相似性（分形）

Song C, Havlin S, Makse H A, Self-similarity of complex network, Nature, 2005, 433:392

复杂网络的自相似性（分形）

重整化

后

Song C, Havlin S, Makse H A, Self-similarity of complex network, Nature, 2005, 433:392

复杂网络的自相似性（分形）

Song C, Havlin S, Makse H A, Self-similarity of complex network, Nature, 2005, 433:392

复杂网络的自相似性（分形）

疾病传播动力学：SI 模型

Infectious Susceptible contact

易受感染者传染者

接触数目

∝ I×S

i(t):群体中t时刻处于I态的密度 s(t):群体中t时刻处于S态的密度

λ : 传染概率

⎧ d s (t ) ⎪ d t = − λ i (t ) s (t ) ⎪ ⎪ d i (t ) = λ i (t ) s (t ) ⎨ ⎪ dt ⎪ i (t ) + s (t ) = 1 ⎪ ⎩

疾病传播动力学：SIS 模型

S (i ) + I ( j ) → I (i ) + I ( j ) I (i ) → S (i )

i(t):群体中t时刻处于I态的密度 s(t):群体中t时刻处于S态的密度

u : 治愈概率

: 传染概率

ds (t ) = − λ i (t ) s (t ) + ui (t ) dt di (t ) = λ i (t ) s ( t ) − ui ( t ) dt i (t ) + s (t ) = 1

存在一个阈值

λc λ > λc

时定态解 i (T)>0 T 为达到稳定态的时间

疾病传播动力学：SIR 模型

S (i ) + I ( j ) → I (i ) + I ( j ) I (i ) → R(i )

i(t):群体中t时刻处于I态的密度 s(t):群体中t时刻处于S态的密度 r(t):群体中t时刻处于R态的密度

u : 免疫概率

λ : 传染概率

⎧ d s (t ) ⎪ d t = − λ i (t ) s (t ) ⎪ ⎪ d i (t ) = λ i (t ) s (t ) − u i (t ) ⎪ ⎨ dt ⎪ d r (t ) = u i (t ) ⎪ ⎪ dt ⎪ i (t ) + s (t ) = 1 ⎩

λ λc 传染爆发并变为全局性的

疾病传播动力学：规则-复杂网络（拓扑机构）

SIS Model

疾病传播动力学：规则-复杂网络（拓扑机构）

SIR Model

疾病传播动力学：小世界网络上的传播

（SIS Model）被感染节点的密度随时间的演化满足如下方程

d ρ (t ) = − ρ ( t ) + λ k ρ ( t ) (1 − ρ ( t ) ) dt

λc = k

−1

ρ = 0, when λ

SIR Model 结论一样

疾病传播动力学：无标度网络上的传播

（SIS Model）被感染节点的密度随时间的演化满足如下方程

d ρk ( t ) = − ρ k ( t ) + λ k ⎡1 − ρ k ( t ) ⎤ ∑ P ( k ' | k ) ρ k ' ( t ) ⎣ ⎦ ' dt k

右边第一项描述由于单位恢复率导致的感染群体的湮灭；第二项为产生项，正比于感

得出流行病传播的阈值为

SIR Model 结论一样

k2 = ∞

P(k ) ~ k −γ , γ ≤ 3

λc → 0

疾病传播动力学：规则-复杂网络（拓扑机构）

气液两相流流型复杂网络

两相流动态实验

天津大学多相流实验室

利用自行研制的纵向多极阵列电导式传感器采集两相流动态波动信号

气液两相流流型复杂网络

泡状流

泡状-段塞过渡流型

0 .0 4 0 .0 0 -0 .0 4 0 .3 0 .0

段塞流

U s w = 0 .1 8 m /s ,U s g= 0 .0 1 m /s

段塞-混状过渡流型

B u b b le f lo w

混状流

U s w = 0 .1 8 m /s ,U s g = 0 .0 4 m /s

B u b b le -s lu g tr a n s itio n a l f lo w

Signals (volt)

-0 .3 0 .6 0 .0 -0 .6 0 .8 0 .0 -0 .8 0 .8 0 .0 -0 .8 0 2 4 6 8 10 12 14 16 18 20

U sw = 0 .1 8 m /s,U sg = 0 .1 2 m /s

S lu g f lo w

U sw = 0 .1 8 m /s,U sg = 0 .3 5 m /s

S lu g - c h u r n tra n s itio n a l f lo w

U sw = 0 .1 8 m /s,U sg= 0 .6 1 m /s

C h u r n f lo w

Time (s)

五种典型气液两相流流型的电导波动信号

气液两相流流型复杂网络

流型复杂网络

气液两相流流型复杂网络

时频域特征提取

时域特征提取：最大（小）值、均值、标准差、非对称系数、峭度系数。频域特征提取：线性预估器四个系数

C-C算法确定最佳延迟时间

C ( m, N , r , τ ) =

2 ∑ θ r − Xi − X j M ( M − 1) 1≤i

{

}

序列长度N

1000 2000 5000 6000 9000 10000

1 S (m, N , r , 2) = {[C1 (m, N / 2, r , 2) − C1m (1, N / 2, r , 2)] + (C2 (m, N / 2, r , 2) − C2 m (1, N / 2, r , 2))} 2

S (m, N , r , t ) =

ΔS (m, t ) = max {S (m, rj , t , N )} − min {S (m, rj , t , N )}

1 5 Δ S (t ) = ∑ Δ S ( m , t ) 4 m=2

1 t ∑ {Cs (m, N / t , r , t ) − Csm (1, N / t , r , t )} t s =1

ΔS(t)

0.20

C-C Method

0.16 0.12 0.08 0.04 0.00 0 20 40 60

最佳延迟时间应该是Δ S (t ) 首次到达最小值所对应的时间 τ d 。

t =

τd τs

100 120 140 160

气液两相流流型复杂网络

Gao Z K and Jin N D, Phys. Rev. E 79: 066303 (2009)

十个时域特征量相关性因子

Cij =

∑ ⎡T (k ) − ⎣

k =1 i

⎤ ⎣ Ti ⎦ ⋅ ⎡ Tj (k ) − Tj ⎤ ⎦

∑ ⎡ T (k ) − ⎣

k =1 i

Ti ⎦ ⋅ ⎤

∑ ⎡T (k ) − ⎣

k =1 j

Tj ⎤ ⎦

0.35

流型复杂网络邻近矩阵Dij及相关性阈值判据rc

0.30 0.25 0.20 0.15 0.80

τ=9 Δt τ=7 Δt τ=5 Δt τ=17 Δt τ=25 Δt

rc=0.98

⎧1, ⎪ Dij = ⎨ ⎪0, ⎩

( Cij ≥ rc ) ( Cij

0.85

0.90

0.95

1.00

气液两相流流型复杂网络

1 1

基于K-means聚类的社团探寻算法基于数据场理论的社团探寻算法

实际网络-Zachary网络社团结构图社团结构不明显的网络--Newman等人在提出的拥有4个社团且其大小均为32的算例网络结构

气液两相流流型复杂网络

Gao Z K and Jin N D, Phys. Rev. E 79: 066303 (2009)

流型复杂网络社团结构

发现了网络中对应于泡状流、段塞流及混状流的三个社团和对应于两种过渡流型的社团间联系紧密节点，从而实现了垂直气液两相流流型识别。

气液两相流流型复杂网络

流型复杂网络社团结构探寻采用基于K-means聚类的网络社团探寻算法分析油水两相流流型复杂网络，寻找网络中联系紧密的节点族。

流型复杂网络社团结构图绘制采用网络可视化软件UCINET和NETDRAW绘制所探寻到的流型复杂网络社团结构图。

基于流型复杂网络社团结构的两相流流型辨识流程图

复杂网络理论及其应用课件(2011-4-13)

相关内容

热门内容

标签