正在加载图片...
,116 北京科技大学学报 第31卷 1.2 随机选择一个节点（节点度为275）为起始点来 搜索含有1250个成员的社团，得到局部社团外部 0.8 链接度L随着社团成员数t的变化关系图，如图9 0.6 所示，从图9中可以看到，在第263,309,344和428 0.4 等17个节点处的社团结构较为显著 ◆一本算法 0.2 一Clauset算法 300r 15202303540 250 起始节点 200 伤 图7本文算法和Clauset算法对Zachary俱乐部网络搜索社团成 100 员的正确率 Fig.7 Rates of correctly classified vertices using the Zachary club network by Clause algorithm and the proposed method 200 400600800100012001400 社团的成员数 从图7中可以看到，本算法中搜索社团成员全 图9局部社团外部链接度随者社团成员数的变化关系 对的有16个节点，Clauset算法全对的有13个节 Fig.9 Relation of the outer link degree of a local community with 点；本算法中有7个起始节点的正确率高于Clauset the number of community vertices 算法，有l0个起始节点的正确率低于Clauset算法， 此外，本算法的34个节点的平均正确率为0.9246， 分析本算法推测到的局部社团和实际情况是否 高于Clauset算法的平均正确率0.9228.因此，两种 一致.在图8中三角形节点表示起始节点所在的社 算法的正确率基本上差不多.Clauset算法运行的平 团.由于起始节点所在的社团中节点度为1的节点 均时间为0.16s,本算法运行的平均时间为0.009s, 较多，而起始节点的节点度又比较大，因此从起始点 可见本算法运行时间明显少于Clauset算法， 开始，局部社团外部链接度L随着社团成员的增加 3.3电信社群网络 而逐步减小到局部最小值.从图8中可以看到许多 本文的数据是从某市移动电信运营商的计费信 这样类似的社团结构，这恰好与图9中L呈现出多 息系统中抽取某段时间发生的64万条通话记录，共 个从局部最大值逐渐减小到局部最小值的变化曲线 包含41万个电话号码，将通话的电话号码作为图 相吻合 的节点，通话关系作为无向图的边，即如果A呼叫 另外，使用本算法和Clauset算法分别选择100 了B,那么就表示A认识B,并且B也认识A·由于 个不同的起始节点来搜索1250个社团成员，得到 选取的数据是某段时间的通话记录，因此网络中含 100个起始节点运行时间的平均值曲线，如图10所 有大量的节点度（即与该节点相连的边数）为1的节 示.从图10中可以看出，搜索的社团成员数越大， 点，整个网络图中含有连通子图4108个.本文选 本算法在计算时间上越优于Clauset算法，随机选 择其中最大的一个子图进行分析，该子图含有 取了图8中的100个节点，其中包含20个边界点， 51430个节点，65021条边，节点度平均值为2，节点 实验结果显示，本算法与Clauset算法对这些节点探 度标准偏差为10，其局部网络图如图8所示 测到的社团结构是相同的， 350 300 250 C1auet算法 200 本算法 150 100 50 图8包含51430个节点的子图中的部分网络结构（三角形的节 200 400 600800100012001400 针相的成员数 点表示起始节点所在的社团) Fig.8 A portion of community structure of the subgraph including 图10本文算法和Clauset算法运行时间对比 51 430 vertices (triangles indicate the community structure of the Fig.10 Processing time by the proposed method and Clauset algo- source vertex) rithm图7 本文算法和 Clauset 算法对 Zachary 俱乐部网络搜索社团成 员的正确率 Fig．7 Rates of correctly classified vertices using the Zachary club network by Clause algorithm and the proposed method 从图7中可以看到本算法中搜索社团成员全 对的有16个节点Clauset 算法全对的有13个节 点；本算法中有7个起始节点的正确率高于 Clauset 算法有10个起始节点的正确率低于 Clauset 算法． 此外本算法的34个节点的平均正确率为0∙9246 高于Clauset 算法的平均正确率0∙9228．因此两种 算法的正确率基本上差不多．Clauset 算法运行的平 均时间为0∙16s本算法运行的平均时间为0∙009s 可见本算法运行时间明显少于 Clauset 算法． 图8 包含51430个节点的子图中的部分网络结构（三角形的节 点表示起始节点所在的社团） Fig．8 A portion of community structure of the subgraph including 51430 vertices （triangles indicate the community structure of the source vertex） 3∙3 电信社群网络 本文的数据是从某市移动电信运营商的计费信 息系统中抽取某段时间发生的64万条通话记录共 包含41万个电话号码．将通话的电话号码作为图 的节点通话关系作为无向图的边即如果 A 呼叫 了 B那么就表示 A 认识 B并且 B 也认识 A．由于 选取的数据是某段时间的通话记录因此网络中含 有大量的节点度（即与该节点相连的边数）为1的节 点．整个网络图中含有连通子图4108个．本文选 择其中最大的一个子图进行分析．该子图含有 51430个节点65021条边节点度平均值为2节点 度标准偏差为10其局部网络图如图8所示． 随机选择一个节点（节点度为275）为起始点来 搜索含有1250个成员的社团得到局部社团外部 链接度 L 随着社团成员数 t 的变化关系图如图9 所示．从图9中可以看到在第263309344和428 等17个节点处的社团结构较为显著． 图9 局部社团外部链接度随着社团成员数的变化关系 Fig．9 Relation of the outer link degree of a local community with the number of community vertices 分析本算法推测到的局部社团和实际情况是否 一致．在图8中三角形节点表示起始节点所在的社 团．由于起始节点所在的社团中节点度为1的节点 较多而起始节点的节点度又比较大因此从起始点 开始局部社团外部链接度 L 随着社团成员的增加 而逐步减小到局部最小值．从图8中可以看到许多 这样类似的社团结构这恰好与图9中 L 呈现出多 个从局部最大值逐渐减小到局部最小值的变化曲线 相吻合． 图10 本文算法和 Clauset 算法运行时间对比 Fig．10 Processing time by the proposed method and Clauset algorithm 另外使用本算法和 Clauset 算法分别选择100 个不同的起始节点来搜索1250个社团成员得到 100个起始节点运行时间的平均值曲线如图10所 示．从图10中可以看出搜索的社团成员数越大 本算法在计算时间上越优于 Clauset 算法．随机选 取了图8中的100个节点其中包含20个边界点 实验结果显示本算法与 Clauset 算法对这些节点探 测到的社团结构是相同的． ·116· 北 京 科 技 大 学 学 报 第31卷