Ch5 复杂网络中的社团结构

第五章复杂网络中的社团结构1社团结构的描述性定义网络中的节点可以分成组，组内连接稠密而组间连接稀疏25.1社团结构的定义社团结构的数学描述派系→k-派系社团K-core子图k-派系社团LS集3社团结构的比较性定义强社团定义要求社团内的每一个节点与社团内其他所有节点都有连接，即每个节点的度数在社团内达到最大。弱社团定义要求社团内的每一个节点与社团外的节点连接数少于与社团内的节点连接数，即社团内部连接比外部连接更密集。4检验划分方法的经典网络人工网络GNBenchmarkLFRBenchmark一些实际网络55.2划分结果的检验与比较LFRbenchmark

6GNBenchmark网络是由128个顶点构成的网络，这128个顶点被平均分成四份，构成四个社团，每个社团包含32个顶点。每个顶点度的期望值为16，Zin表示顶点与社团内部顶点连边数目的期望值，Zout表示顶点与社团外顶点连边数目的期望值，从而Zin+Zout=16.Zout越小说明顶点与社团外部的连接越少，网络的社团结构越明显；Zout越大说明网络越混乱，社团结构越不明显。对于Zout值大的网络还能够基本正确的对网络进行划分的算法，在实际应用中适用范围更广，价值更大。7实际网络空手道俱乐部网科学家合作网美国大学足球赛季网猴子网…8划分结果的比较方法正确划分率比较法共同信息比较法D函数比较法9模块度函数

105.3基于模块度优化的社团划分算法在社团结构的划分过程中，计算每一种划分所对应的模块度值，并找出数值尖峰所对应的划分（通常会有一两个），这就是最好或最接近期望的社团结构划分方式11优化模块度函数（Q函数）算法Newman贪婪算法（1）初始时将网络中的每一个节点都视为一个社团，每个社团内只有一个节点。即如果网络中共有n个节点，则初始有n个社团。（2）两两合并社团，并计算社团合并所产生的Q值的变化量：

选择使得Q值增加最大（或减少最小）的方式进行合并。（3）重复步骤（2）的操作，不断对社团进行合并，直到所有节点被集聚到一个社团中为止。12优化模块度函数（Q函数）算法Newman贪婪算法的检验13改进的Newman贪婪算法（复杂度更低）14极值优化算法（1）任意将网络中的节点分成等大的两部分，每部分中相互连通的节点形成一个社团，从而形成一个初始的社团结构。（2）根据社团结构计算每个节点的适合度，并将适合度最低的节点归入另一部分中，这可能使得社团结构发生巨大的变化。计算新社团结构的函数值，并按照新的社团结构重新计算每个节点的适合度。（3）重复步骤（2），直到得到最大的函数值为止。断开两部分之间的所有连边，从而将网络划分成两个社团。（4）对得到的社团递归地重复上述步骤（1）至（3）的操作，当函数值不能被进一步增大时，就得到了网络社团的最优划分。15极值优化算法划分过程示意图16极值优化算法检验17层次聚类法由距离最近、相似度最高的社团开始合并，直到将所有元素都归属于一个社团为止用结构等价的程度来衡量两个节点的相似度：如果一个顶点与网络中其余顶点的连接方式和另一顶点与网络中其余顶点的连接方式完全相同，则这两个顶点结构等价用欧几里德距离度量衡量顶点i，j间的距离为在进一步的凝聚过程中，由于每个社团所包含的元素不再唯一，因此要定义包含多个元素的社团间的距离，常用的方法有：最短距离法、最长距离法、平均距离法185.4基于网络拓扑结构的算法GN算法由网络中社团的定义可知，所谓社团就是指其内部顶点的连接稠密，而与其他社团内的顶点连接稀疏。这就意味着社团与社团之间存在联系的通道比较少，并且要想从一个社团到另一个社团，至少要通过这些通道中的一条。如果能找到这些重要的通道，并将它们移除，那么网络就自然而然的分成了各个社团。用最短路径边介数标记每条边对连通性的重要程度。社团间连边的边介数比较大，因为社团间节点对的最短路径必然通过它们；而社团内部边的边介数则比较小。19GN算法的具体过程：（1）计算网络中各条边的边介数；（2）找出边介数最大的边，并将它移除（如果最大边介数的边不唯一，那么既可以随机挑选一条边断开也可以将这些边同时断开）；（3）重新计算网络中剩余各条边的边介数；（4）重复第（2）、（3）步，直到网络中所有的边都被移除。20边集聚系数法边集聚系数：一条边的边集聚系数定义为网络中包含该边的实际三角形数目与包含该边的所有三角形数目之比，其中包含该边的所有三角形包括实际三角形和潜在三角形。两节点i，j间连边的边集聚系数为连接不同社团的点的边，被较少的三角形包含，或者根本不包含于任何三角形，从而边集聚系数就小。然而社团内部由于有比较稠密的边，所以应该包含较多的三角形，因此连接集团内部的点的边的边集聚系数就大。21修正的边集聚系数：推广到更大的环：22边集聚系数法具体过程（1）首先确定研究环的种类（三角形、四边形……）；（2）根据定义计算每条边的边集聚系数，断开边集聚系数最小的边；（3）重复计算边集聚系数和执行断边的操作，直到网络中所有的边都被断开为止23谱分析算法主要思想：通过对由邻接矩阵形成的拉普拉斯矩阵(LaplacianMatrix)或标准矩阵(NormalMatrix)的特征值、特征向量的分析，挖掘网络中的社团结构以标准矩阵的分析为例，由于标准矩阵行的标准化，标准矩阵总有最大的特征值等于1，以及与之对应的特征向量（1，1，1……）在对社团化明显的网络的分析中发现，如果网络自然呈现m个社团，则标准矩阵就有m-1个十分接近1的特征值，而其余的特征值则有较大的距离。最大的特征值所对应的特征向量有一个特性：在同一个社团中的顶点所对应的值较为接近。因此，特征向量中元素的值呈现阶梯状分布，并且阶梯的级数与社团的个数相匹配。2425一个社团结构清晰的网络特征向量中节点对应数值同样的方法也可以对拉普拉斯矩阵进行分析。差别在于，拉普拉斯矩阵总存在平庸的特征值0，考察的标准是大于0的最小的特征值及其对应的特征向量。26电流算法将网络的边视为阻值相等的电阻，在两顶点i,j上施加一个固定的电压，如节点i的电势为1，节点j的电势为0，从而整个网络就成了一个电路，每个节点上都会有相应的电势值，进而按照电势值划分节点所属的社团。同属一个社团的节点，其电势值应当比较接近，而与其他社团节点的电势值相差较多.275.5基于网络动力学的算法随机游走算法假设网络上有一个可以任意跳跃到其邻居位置上的粒子，它每一步跳跃都只与其当时所处的位置有关，而与之前的状态没有关系，即一系列跳跃形成一个马尔科夫链。由节点i跳跃到其邻居节点j的概率，从而得到节点间的一步转移概率矩阵（TransitionMatrix）P；由节点间的一步转移概率矩阵可以得出节点间的t步转移概率矩阵Pt。两节点结构等价的程度由距离rij衡量:如果两个顶点同属于一个社团，那么分别从两个顶点透视整个网络得到的结果应该相近。应用这种距离也可以将网络梳理成树状图的形式，并应用函数得到最优的社团结构28Potts模型算法网络中的顶点与模型中的粒子相对应，并对模型的哈密顿量(Hamiltonian)进行修正。当修正后的哈密顿量处于基态时，具有相同自旋(spin)值的粒子归为一个社团。29

30派系过滤算法社团间存在重叠节点的4-派系社团315.6重叠社团的划分算法具体方法（1）基于网络中各节点的度可以判断出网络中可能存在的最大全耦合网络的大小s。（2）从网络中一个节点出发，找到所有包含该节点的大小为s的派系后，为了避免多次找到同一个派系，删除该节点及连接它的边。（3）然后，另选一个节点，重复上面的步骤直到网络中没有节点为止。至此，找到了网络中大小为s的所有派系。（4）接着，逐步减小s（每一次s减小1），再用上述方法，便可以寻找到网络中所有不同大小的派系。其中，采用迭代回归的算法，从一个节点v出发寻找包含它的所有大小为s的派系。32边聚类算法将具有一定相似度的连边合并为一个社团具体方法：（