复杂网络基本概念_什么是复杂网络[通俗易懂]

大家好，欢迎来到IT知识分享网。

1.复杂网络：随机网络，小世界网络和无标度网络
2.小世界网络的属性：平均路径长度（Average Path Length,APL）小于正则网络的；小世界网络具有较低的平均聚类系数（Average Clustering Coefficient,ACC）
3.复杂网络面对的挑战：高数据量；物理系统到真实复杂网络模型映射过程中的复杂性；高计算复杂性
4.图信号处理将经典信号处理中的概念和工具（如平移，卷积，傅里叶变换，滤波器组和小波变换）扩展应用于任意网络中的数据
5.加权图，有向图
6.图在计算机的存储器中用矩阵表示，如邻接矩阵，关联矩阵，权重矩阵，度矩阵以及拉普拉斯矩阵等。
7.如果在两个节点之间存在多条边，称该图为多重图（multigraph）;如果存在自环，则称该图为伪图（pseudograph）
8.包含原始图所有顶点的子图称为生成子图（spanning subgraph）
9.图g的补图是指与图G具有同样的顶点集，但边集中的边则由那些在图g中不存在的边组成，也称为反向图（inverse graph）
10.图在计算机中以矩阵或者链表的方式存储
11.权重矩阵：图的权重矩阵包含图中相应边的权重。权重矩阵是图的拓扑结构的完整表示。所有的其他矩阵（邻接，度，拉普拉斯）都可以通过权重矩阵推导得出。对于非加权图，权重矩阵和邻接矩阵是一样的。
12.邻接矩阵：包含图连接的N*N矩阵
13.关联矩阵：每一行对应图中的一个顶点，而每一列对应图中的一条边。
14.度矩阵：是一个对角线矩阵，在对角线上包含了顶点的度。节点的度是所有与该节点相关联的边的权重之和。一些大的网络通常通过度的频率分布来刻画。
15.拉普拉斯矩阵：L=D-W，D是图的度矩阵，W是图的权重矩阵。具有正边权重的无向图的拉普拉斯矩阵的基本性质:对称性；每一行之和为0，具有奇异性，det(L)=0；半正定；其特征值是非负实数。
16.归一化拉普拉斯矩阵：L^(norm)=D(-1/2)LD^(-1/2)
17.有向拉普拉斯矩阵：L=Din-W; Din是入度矩阵
18.基本图测度：平均邻居度（AND），平均聚类系数（ACC，局部连通性属性），平均路径长度（APL，全局网络属性），平均边长度（AEL），图的直径和体积。
19.在随机网络中，APL值远小于正则网络，其原因在于该网络中节点之间的连接具有随机性特征。小世界网络介于正则网络和随机网络之间，包含了两个网络的最佳特性。小世界网络具有较低的APL值和中等的ACC值。
20.平均边长度：可以通过网络中每条边的长度之和与总边数之间的比值来衡量。
21.图的直径：图中任意两个顶点之间距离的最大值；图的体积：表示所有顶点度的和。
22.图的基本定义和属性：①途径，路径以及回路②连通性：若图中任意节点对之间均存在一条路径，则称该图是连通的；图的顶点（边）连通度是指为使图变得不连通所需的最小节点（边）数目；图的割点是一个顶点，当移除该顶点后图将变得不连通；若某条边被移除后使得图变得不连通，则该边称为图的桥（bridge）；在一个图中，最大的不可分子图称为块（block）；割：一个连通图的割是边或者顶点的一个子集，移除该子集将导致图不连通；无环图指一个图不包含回路或者环。DFS，深度优先搜索
23.同构（isomorphism）：两个图具有相同的顶点数，并且这些顶点具有相同的连接方式，则称他们同构
24.平面性：若图能在一个平面上绘制并且任意两条边之间不存在相交，则称该图为平面图。（平面嵌入planar embedding）
25.欧拉公式：如果一个连通平面图G具有N个节点，E条边和F个面，则
N-E+F=2
26.可着色性（五色定理和四色猜想）
27.可遍历性：如果某个图存在包含所有顶点但不重复经过边的路径，则称该图为可遍历的。
28.欧拉图：给定一个图，确定是否存在经过所有顶点并在起始点结束的途径，并且恰好遍历每条边一次，这样的图称为欧拉图。一个图是欧拉图当且仅当图的所有顶点的度为偶数。至少一个顶点的度为奇数，则该图不可能是欧拉图。
29.哈密顿回路：遍历图的所有顶点恰好一次的途径称作哈密顿路径。如果哈密顿路径结束于起始点，则称为哈密顿回路。一个包含哈密顿回路的图称为哈密顿图。
30.网络流：我们希望找出每分钟能够进入和离开该网络的最大卡车数目，该问题即为经典的最大流问题。流图是一个有向图，其中给出了两个特殊的节点–源节点和汇聚节点。最大流问题也可被叫做最小割问题。
31.最大流最小割定理：在具有单个源节点和单个汇聚节点的网络中，从源节点到汇聚节点的最大可能流量等于网络中所有可能的割中的最小割容量。
32.乘积图：考虑两个分别具有N1和N2个节点的图g1=(v1,w1)和g2=(v2,W2)。乘积图是一个具有N1N2个顶点的图。其权重由w1,w2所导出。克罗内克积,笛卡尔积，强积。
33.图的类型：正则图，二分图，树，完全图以及线图等。
34.正则图：每个节点的邻接节点的数目是相等的。如果在正则图中每个顶点的度是r，则称为r-正则图。
35.二分图可以将图划分为不相交的集合。
36.完全图：每个节点都与图中所有其他节点相连接。在一个具有N个节点的完全图中，每个顶点的度是N-1,且总的边数为N(N-1)/2.
37.树：是一个不包括回路的连通图。生成树。最小生成树（边权重之和最小的生成树）。Kruskal MST算法。
38.线图：图g的线图L（g）是将原始图g的边变换为顶点。
39.冲突图
40.图的其他重要测度：Cheeger常数，团（图中的一个完全子图称为团）数，图寻路算法，dijkstra最短路径算法，所有节点对之间的最短路径算法。

第三章复杂网络概述
1.现有的真实世界复杂网络可以大致分为三类：随机网络，小世界网络以及无标度网络。
2.复杂网络的测度：平均邻居度，平均路径长度，网络直径，平均聚类系数，度分布，中心性测度，度度相关性，节点临界性，网络电阻距离。
3.平均邻居度（Average Neighbor Degree,AND）：网络中所有节点的度的平均值。用于确定网络类型。刻画了网络的局部特性。
4.平均路径长度（Average Path Length,APL）:全局测度。是网络中所有可能节点对之间的端到端路径长度的平均值。
5.网络直径：降低网络直径有利于改善网络中的传输延迟。
6.平均聚类系数（Average Clustering Coefficient,ACC）:用来刻画网络的健壮性和冗余性。ACC越高，说明网络被断开的机会就越少。
7.度分布：小世界网络的度服从高斯分布，无标度网络的度服从幂律分布。
8.中心性测度：理解网络结构和动态特性，度中心性，接近中心性，介数中心性，图中心性，特征向量中心性，GFT中心性。
9.度中心性（Degree Centrality,DC）：所有与该节点关联的边的权重之和。
10.接近中心性（Closeness Centrality,CC）:描述了一个节点与其他节点的接近程度。CC还度量了在有向网络中的其他节点扩散信息时节点的重要性。
11.介数中心性（Betweenness Centrality,BC）：刻画节点在实现网络长距离通信中的重要性。
12.图中心性（Graph Centrality,GCmetric）：基于节点级的信息来标识网络的中心化程度。
13.特征向量中心性（Eigenvector Centrality ,EC）：根据相邻节点的中心性来对其进行加权。
14.GFT中心性：GFT，graph fourier transform，图傅里叶变换。GFT中心性同时考虑给定节点的局部影响和全局影响。利用图谱来确定节点在图中的中心性。
15.复杂网络中的度—度相关性：度-度相关性描述了一个相互连接的节点对之间的关系，据此可以将网络划分为：同配网络（assortative network）和异配网络(disassortative network)。
16.节点临界性：通过节点权重归一化后的节点随机游走介数。
17.网络电阻距离：表示将所有的边替换为代表性电阻所得到的节点间的等效电阻。
18.复杂网络的社区发现：三种典型的方法：模块度最大化，Surprise最大化以及基于冲突图变换的社区发现（CTCD）
19.模块度最大化：模块度M表示位于社区内的边减去边在没有社区结构而随机分布情况下的期望。
20.Surprise最大化：S取决于每个社区内的链路数和节点数。
21.复杂网络中的熵：熵度量了消息中所包含的平均信息量。熵提供了一个很好的描述手段来刻画链路和节点的特征。
22.网络熵：定义为对网络不确定性的一个度量。
23.节点度熵（Nodal Degree Entropy,NDE）：基于节点的邻居度计算得到。对于评价邻居意义上的节点异构性非常有效。
24.链路长度变化熵（Link Length Variability Entropy,LLVE）:度量了复杂网络中链路长度的变化情况。
25.链路影响熵LInE:除了度量节点的重要性，还可以用于计算网络影响的稳定性。根据来评价，复杂网络具有如下的顺序，正则网络>小世界网络>ER网络>无标度网络>空间无线网络。
26.动态网络中的LInE行为：链路影响的变化决定了节点的不稳定性，若网络中随时间发生变化的链路较少，则节点在网络中更稳定。基于度的方法无法区分节点影响，不能有效观察节点影响的变化，而基于LInE可以有效地度量不同时刻链路影响的变化，并且能够正确估计节点影响的稳定性。
27.随机网络：随机网络的演进：根据已定的总的链路数；在节点对之间创建的概率已定。
28.ER随机网络模型的创建：N个节点基于概率P随机地进行连接。
29.随机网络的属性：包括期望网络规模，平均邻居度，网络直径，平均路径长度，聚类系数，度分布，巨型分支的形成。
30.巨型分支的形成：当p的值增加时，随机网络的连通性也得到了加强，逐渐演进出一个大的节点簇，这个节点簇包含大量的连接，可以称为巨型分支。
31.开放性研究问题：复杂网络的一个具有挑战性的问题是高效地检测社区；设计和开发更快的算法来估计APL仍然是一个开放的研究问题；提出一个统一的中心性测度，既具有较低的时间复杂度，又能够用于判别节点的局部和全局影响；复杂网络中现有的社区发现算法经常试图找到严格不相交的社区，需要设计新的测度来描述这种重叠参与的情况，需要设计新的算法以有效识别社区及其重叠情况；ER模型不能描述许多真实世界随机网络的形成以及演进行为，设计开发新的能够解释时间依赖网络演进的网络模型仍然是一个开放的研究问题。