第1期 王立敏等：基于最小社团链接度增量的社团结构挖掘算法 ,115, t的函数关系图，如图3所示.图3中每一条曲线都 2.5 是由100个随机图平均得到的，为了清楚起见，只 2.0 在图中列出了p"为1到7等七种情况下的函数关 Clauset算法 系.，从图中可以看出，在这七个曲线图中，p值越 小，在t=(32,64,96,128)时，L达到局部最小的特 1.0 征越明显，四个局部社团结构也比较显著；随着p 本算法 的增长，L的波谷高度也在不断地增加，四个局部 20 40 6080 100 120 140 社团结构也越来越不明显.特别地，当p=7时， 社州的成员数 网络中存在的四个局部社团结构已经不太明显了· 图5本算法和Clauset算法对计算机生成的网络图搜索社团成 因此通过图3可以充分地说明用局部社团外链接度 员的运行时间 L来衡量局部社团结构的显著性是可行的 Fig.5 Relations of processing time to the number of community 700 vertices by the proposed method and Clauset algorithm +1 600 2 34 3.2 Zachary空手道俱乐部 下面举例来考查本算法和Clauset算法在社会 200 9 网络中的应用，事例出自社会网络分析的一个经典 问题1.20世纪70年代初期，Zachary用了两年的 时间来观察美国一所大学中的空手道俱乐部成员间 20 406080 100120 140 社团成员数 的相互社会关系，基于这些成员在俱乐部内部以及 外部的社会关系，他构造了他们之间的关系网，如 图3p取不同值时局部社团的外部连接度L与搜索社团成员 图6所示.事有凑巧，在调查过程中，该俱乐部的主 数：的函数关系图 管与校长之间因是否抬高俱乐部收费的问题产生了 Fig.3 Relations of the outer link degree of a local community with 争执.结果，该俱乐部分裂成了两个分别以主管和 the number of community vertices at different values of p 校长为核心的小俱乐部.图中节点1和节点33分 同时，把Clauset算法也应用到不同pu值随机 别代表了俱乐部主管和校长，而红色和蓝色的节点 生成的100个网络图中，对每一个图选择从第1个 也分别代表了分裂后的小俱乐部中的各个成员，在 到第128个节点作为起始节点来搜索128个社团成 复杂网络的社团结构分析中，Zachary网络已经成为 员，得到两种算法搜索社团成员的平均正确率的对 一个很好地用于比较挖掘网络社团结构算法准确性 比图和运行执行情况图，如图4和图5所示.图4 的经典网络 显示本算法在p=4之前两种算法的平均正确率 基本差不多，而在put=4之后差于Clauset算法， 图5中曲线的运行时间是128个点搜索社团成员所 需时间的平均值.从图5可以看出，本算法在运行 时间上与Clauset算法相比得到了显著地提高， 12 1.0 Clauset算法 0.8 本算法 图6 Zachary空手道俱乐部分裂的关系网络（方形和圆形分别表 0.6 0.4 示分裂后两个小俱乐部的成员) 0.2 Fig.6 Splitting of the Zachary club network (squares and circles in- 0 dicate the two communities observed by Zachary) 值 图7给出了本算法和Clauset算法对34个起始 图4本算法和Clauset算法搜索社团成员的正确率 节点搜索社团成员的正确率的对照曲线，图中横轴 Fig.4 Rates of correctly classified vertices by the proposed method 表示34个起始节点，纵轴表示每个起始节点搜索社 and Clause algorithm 团成员的正确比率，t 的函数关系图‚如图3所示．图3中每一条曲线都 是由100个随机图平均得到的．为了清楚起见‚只 在图中列出了 p out为1到7等七种情况下的函数关 系．从图中可以看出‚在这七个曲线图中‚p out值越 小‚在 t＝（32‚64‚96‚128）时‚L 达到局部最小的特 征越明显‚四个局部社团结构也比较显著；随着 p out 的增长‚L 的波谷高度也在不断地增加‚四个局部 社团结构也越来越不明显．特别地‚当 p out＝7时‚ 网络中存在的四个局部社团结构已经不太明显了． 因此通过图3可以充分地说明用局部社团外链接度 L 来衡量局部社团结构的显著性是可行的． 图3 p out取不同值时局部社团的外部连接度 L 与搜索社团成员 数 t 的函数关系图 Fig．3 Relations of the outer link degree of a local community with the number of community vertices at different values of p out 同时‚把 Clauset 算法也应用到不同 p out值随机 生成的100个网络图中‚对每一个图选择从第1个 到第128个节点作为起始节点来搜索128个社团成 员‚得到两种算法搜索社团成员的平均正确率的对 比图和运行执行情况图‚如图4和图5所示．图4 显示本算法在 p out＝4之前两种算法的平均正确率 基本差不多‚而在 p out ＝4之后差于 Clauset 算法． 图5中曲线的运行时间是128个点搜索社团成员所 需时间的平均值．从图5可以看出‚本算法在运行 时间上与 Clauset 算法相比得到了显著地提高． 图4 本算法和 Clauset 算法搜索社团成员的正确率 Fig．4 Rates of correctly classified vertices by the proposed method and Clause algorithm 图5 本算法和 Clauset 算法对计算机生成的网络图搜索社团成 员的运行时间 Fig．5 Relations of processing time to the number of community vertices by the proposed method and Clauset algorithm 3∙2 Zachary 空手道俱乐部 下面举例来考查本算法和 Clauset 算法在社会 网络中的应用．事例出自社会网络分析的一个经典 问题［14］．20世纪70年代初期‚Zachary 用了两年的 时间来观察美国一所大学中的空手道俱乐部成员间 的相互社会关系．基于这些成员在俱乐部内部以及 外部的社会关系‚他构造了他们之间的关系网‚如 图6所示．事有凑巧‚在调查过程中‚该俱乐部的主 管与校长之间因是否抬高俱乐部收费的问题产生了 争执．结果‚该俱乐部分裂成了两个分别以主管和 校长为核心的小俱乐部．图中节点1和节点33分 别代表了俱乐部主管和校长‚而红色和蓝色的节点 也分别代表了分裂后的小俱乐部中的各个成员．在 复杂网络的社团结构分析中‚Zachary 网络已经成为 一个很好地用于比较挖掘网络社团结构算法准确性 的经典网络． 图6 Zachary 空手道俱乐部分裂的关系网络（方形和圆形分别表 示分裂后两个小俱乐部的成员） Fig．6 Splitting of the Zachary club network （squares and circles in￾dicate the two communities observed by Zachary） 图7给出了本算法和 Clauset 算法对34个起始 节点搜索社团成员的正确率的对照曲线．图中横轴 表示34个起始节点‚纵轴表示每个起始节点搜索社 团成员的正确比率． 第1期 王立敏等： 基于最小社团链接度增量的社团结构挖掘算法 ·115·