正在加载图片...
第1期 王立敏等：基于最小社团链接度增量的社团结构挖掘算法 .113 团结构，在这种情况下，不希望消耗过多的时间来 团的链接数达到局部最小时，社团的结构才较为显 寻找全部的社团结构，例如：对于犯罪网络，公安部 著，根据该思想，本文提出了局部社团外部链接度 门最想了解的是犯罪集团的头目所接触的犯罪嫌疑 的概念 人（即犯罪头目所属的局部社团结构），以便能更好 地一网打尽整个犯罪团伙；对于疾病传播网络，疾病 控制中心可能想在最短时间内掌握发病的病源所接 触的人群，以便及时切断疾病传播的途径，使疾病的 传播得到有效控制.因此，就产生了在不完全了解 网络整体结构的情况下，对网络的局部社团结构进 行研究的必要性 2005年Bagrow12]提出了一种利用局部信息来 探测整个网络社团结构的方法，称为BB算法，它是 通过由一个起始节点逐层向外扩展的方法，在每一 步执行过程中，判断整个一层总暴露度是否满足当 图1一个小型的具有社团结构性质的网络（网络中的节点自然 地分成三个不同的簇，簇内的节点之间的链接较多，簇之间节点 前设定的阈值，如果满足就把整个一层的节点加入 的链接较少) 到社团中，否则停止，事实上，在复杂网络中社团的 Fig.I Small network with community structure (in this case there 同一层邻居节点有可能属于不同的社团.因此，BB are three communities,denoted by the dashed circles,which have 算法存在的最大缺陷在于它是把社团的整个一层邻 dense internal links but between which there are only a lower density 居节点全部加入到社团或者全部排除在社团之外， of external links) 之后，Clauset[3]提出“局部模块性”的概念，并根据 为了直观地描述社团内部节点之间以及社团内 此概念给出了一个挖掘局部社团结构的算法， 部与外部之间的链接关系，用C表示社团内节点的 Clauset算法是围绕着初始节点每次选择局部模块 集合，v:和表示网络中任意两个节点，C表示社 增量最大的节点加入到社团中的方法，由于局部模 团外节点的集合，则社团C的链接矩阵C表示如 块增量的计算与社团的内外部的链接状况有关，因 下： 此算法的时间复杂度为O(kd),d为节点的平均 1, 节点度，k为将要寻找的社团成员数目， C0, :和相连，且∈C或u,∈C() 其他 本文提出了一个衡量局部社团结构数量特征的 然后，定义局部社团外部链接度L为： 指标一局部社团外部链接度，并给出了一种简单、 L=∑c(ij) (2) 快速挖掘网络局部社团结构的算法 1,:∈C,且∈C:或∈C,且∈C 1相关概念 其中，(i,)一0，其他 社团结构的识别是通过最大化全局社团结构的 局部社团外部链接度是一个从局部角度出发来 数量化指标来实现的，例如，Girvan和Newman提 看社团结构的显著性程度的指标，局部社团外部链 出的衡量网络划分质量的标准一模块性Q,Q的 接度越小，说明局部社团结构越显著 计算需要使用整个网络的链接数m·对于在网络的 通常，局部社团外部链接度L的变化与起始节 整体结构不太清楚的情况下，模块性Q是根本无法 点的度数有关，大致存在两种情况：一种是选择了节 计算的，因此，如果不了解网络结构的全局知识，那 点度数较小的起始节点，从起始节点开始L值较 么社团结构的度量标准就不能使用这种具有全局特 小，随着社团成员的增加而逐步增大，增大到一定值 性的指标.针对这种情况，本文提出了一种衡量局 后又开始减小到局部最小值：另一种是选择了节点 部社团结构数量特征的指标一局部社团外部链接 度数较大的起始节点，从起始节点开始L值就比较 度 大，随着社团成员的增加而逐步减小，一直到达局部 根据Girvan和Newman对社团结构的定义可 最小值，当L达到局部最小值时，局部社团的结构 知，社团内部节点之间的链接程度明显高于社团之 相对比较显著，因此通过L的变化就可以很容易 间的链接程度，如图1所示.当一个社团与其他社 地找到社团的边界，团结构．在这种情况下不希望消耗过多的时间来 寻找全部的社团结构．例如：对于犯罪网络公安部 门最想了解的是犯罪集团的头目所接触的犯罪嫌疑 人（即犯罪头目所属的局部社团结构）以便能更好 地一网打尽整个犯罪团伙；对于疾病传播网络疾病 控制中心可能想在最短时间内掌握发病的病源所接 触的人群以便及时切断疾病传播的途径使疾病的 传播得到有效控制．因此就产生了在不完全了解 网络整体结构的情况下对网络的局部社团结构进 行研究的必要性． 2005年 Bagrow ［12］提出了一种利用局部信息来 探测整个网络社团结构的方法称为 BB 算法．它是 通过由一个起始节点逐层向外扩展的方法．在每一 步执行过程中判断整个一层总暴露度是否满足当 前设定的阈值．如果满足就把整个一层的节点加入 到社团中否则停止．事实上在复杂网络中社团的 同一层邻居节点有可能属于不同的社团．因此BB 算法存在的最大缺陷在于它是把社团的整个一层邻 居节点全部加入到社团或者全部排除在社团之外． 之后Clauset ［13］提出“局部模块性”的概念并根据 此概念给出了一个挖掘局部社团结构的算法． Clauset 算法是围绕着初始节点每次选择局部模块 增量最大的节点加入到社团中的方法．由于局部模 块增量的计算与社团的内外部的链接状况有关因 此算法的时间复杂度为 O（ k 2d）d 为节点的平均 节点度k 为将要寻找的社团成员数目． 本文提出了一个衡量局部社团结构数量特征的 指标———局部社团外部链接度并给出了一种简单、 快速挖掘网络局部社团结构的算法． 1 相关概念 社团结构的识别是通过最大化全局社团结构的 数量化指标来实现的．例如Girvan 和 Newman 提 出的衡量网络划分质量的标准———模块性 QQ 的 计算需要使用整个网络的链接数 m．对于在网络的 整体结构不太清楚的情况下模块性 Q 是根本无法 计算的．因此如果不了解网络结构的全局知识那 么社团结构的度量标准就不能使用这种具有全局特 性的指标．针对这种情况本文提出了一种衡量局 部社团结构数量特征的指标———局部社团外部链接 度． 根据 Girvan 和 Newman 对社团结构的定义可 知社团内部节点之间的链接程度明显高于社团之 间的链接程度如图1所示．当一个社团与其他社 团的链接数达到局部最小时社团的结构才较为显 著．根据该思想本文提出了局部社团外部链接度 的概念． 图1 一个小型的具有社团结构性质的网络（网络中的节点自然 地分成三个不同的簇簇内的节点之间的链接较多簇之间节点 的链接较少） Fig．1 Small network with community structure （in this case there are three communitiesdenoted by the dashed circleswhich have dense internal links but between which there are only a lower density of external links） 为了直观地描述社团内部节点之间以及社团内 部与外部之间的链接关系用 C 表示社团内节点的 集合vi 和 vj 表示网络中任意两个节点C 表示社 团外节点的集合则社团 C 的链接矩阵 Cij 表示如 下： Cij＝ 1 vi 和 vj 相连且 vi∈C 或 vj∈C 0 其他 （1） 然后定义局部社团外部链接度 L 为： L＝ ∑ij Cijδ（ ij） （2） 其中δ（ ij）＝ 1 vi∈C且 vj∈C；或 vj∈C且 vi∈C 0 其他 局部社团外部链接度是一个从局部角度出发来 看社团结构的显著性程度的指标．局部社团外部链 接度越小说明局部社团结构越显著． 通常局部社团外部链接度 L 的变化与起始节 点的度数有关大致存在两种情况：一种是选择了节 点度数较小的起始节点从起始节点开始 L 值较 小随着社团成员的增加而逐步增大增大到一定值 后又开始减小到局部最小值；另一种是选择了节点 度数较大的起始节点从起始节点开始 L 值就比较 大随着社团成员的增加而逐步减小一直到达局部 最小值．当 L 达到局部最小值时局部社团的结构 相对比较显著．因此通过 L 的变化就可以很容易 地找到社团的边界． 第1期 王立敏等： 基于最小社团链接度增量的社团结构挖掘算法 ·113·