面向大规模应用层拓扑的社团发现技术

　　0引言

　　随着复杂网络研究的深入进行，人们发现现实世界网络中普遍存在社团结构。社团结构是指网络可根据其自身的拓扑结构被划分为若干个社团；同一社团内的节点连接紧密，而不同社团间的节点连接稀疏。网络的社团结构有助于人们分析复杂网络的拓扑性质和结构、理解复杂网络中各组成模块的功能、揭示复杂网络中隐藏的规律和预测复杂网络的行为等。目前，社团发现技术已经被广泛应用到网络舆情分析控制等领域。

　　社团发现的历史最早可以追溯到图划分。传统社团发现方法包括图划分方法中的Kernighan-Lin算法和谱平分算法，以及社会学方法中的层级聚类方法和K-Means聚类方法。近几年，又提出了一些新的社团发现算法，比如GN算法[1]、CNM算法[2]、Wakita算法[3]、Louvain算法[4]、模拟退火算法[5]、谱划分方法[6]、派系过滤算法[7]等。

　　现实世界网络的巨大规模对社团发现技术形成了严峻挑战。在已提出的社团发现算法中，绝大部分算法都只能处理几千个节点的网络，而现实世界网络的规模大多在百万个节点以上。这就使得绝大部分社团发现算法在分析现实世界网络方面失去了实际应用价值。Kwak等人[8]已经就社团发现算法的比较开展了一定的研究。为了更为有效地筛选得到具有实际应用价值的社团发现算法，在其工作基础上，本文提出了三个指标来衡量社团发现算法。这三个指标分别是：可扩展性、准确度和敏感度。基于这三个指标，文中使用三个社团发现算法——CNM算法、Wakita算法、Louvain算法——进行了一系列对比实验。通过对实验结果的分析，能够充分理解为什么这三个指标可以体现该算法的实际应用价值，从而为算法的选择以及算法设计提供有益的指导。

　　1衡量指标

　　1.1可扩展性

　　可扩展性用以定性评估社团发现算法所能处理的网络规模大小。随着需要分析处理的网络规模逐渐增大，社团发现算法所消耗的时间也将逐渐增长。因此，可扩展性也可定性地描述为算法所消耗时间随数据规模增大而增长的趋势。可在规模依次增大的多个现实世界网络数据集上运行同一个社团发现算法，计算得出社团发现算法处理每个数据集所消耗的时间。这样，便可以观察到社团发现算法所消耗时间的增长趋势，也就是该社团发现算法的可扩展性。增长趋势越明显，算法的可扩展性越差，算法所能处理的网络规模越小。

　　在筛选具有实际应用价值的社团发现算法的过程中，可扩展性是需要考虑的首个因素。只有具备足够高强的可扩展性，算法才能真正适用于一些规模巨大的网络分析。

　　1.2准确度

　　准确度用于衡量社团发现算法所得出的社团划分结果的质量。尽管存在很多方法来衡量社团划分结果质量，但是Newman和Girvan提出的模块性[1]已经成为事实上的标准。因此，文中将准确度定义为社团划分结果的模块性值。模块性值越大，社团划分结果越好，社团发现算法的准确度越高。

　　模块性的提出基于以下观点：随机图中不存在社团结构。因此，通过对比结果子图的实际边密度和空模型的期望边密度，就能确定图中是否存在社团结构。空模型是原始图的一个副本。除了不包含社团结构外，空模型和原始图的结构属性要基本相同。文中选择的空模型要求模型中每个节点的度和原始图中该节点的度均要保持一致。模块性的计算公式是：

　　Q=12m∑ijAij-kikj2mδ（Ci，Cj）（1）第4期黄振，等：面向大规模应用层拓扑的社团发现技术智能计算机与应用第3卷

　　A是图的邻接矩阵，m是图的边数，ki为节点i的度，Ci是社团划分结果中节点i所属的社团编号。当节点i和j被划分到同一个社团中，即Ci=Cj时，δ（Ci，Cj）的值为1，否则为0。只要遍历图的所有节点对，就能计算得到社团划分结果的模块性Q值。

　　1.3敏感度

　　已经证明，社团发现是NP完全问题。因此，绝大部分社团发现算法都是启发式近似算法。这就导致社团发现算法将存在结果不一致的问题。也就是说，当同一个图的节点输入顺序发生改变时，社团发现算法将在该图上得到不同的划分结果。Kwak等人[8]的研究也得出了相同的结论。当这种不一致性较为明显时，社团发现算法所得出的划分结果将失去参考意义。为了衡量社团发现算法所得划分结果的不一致程度，文中提出了敏感度这个指标。

　　敏感度可通过计算所有划分结果的节点成对概率进行衡定。节点成对概率由Kwak等人[8]提出。通过改变节点的输入顺序，并在同一个图上多次运行某一社团发现算法。由于社团发现算法的结果会出现不一致，就会得到这个图的多个划分结果。节点成对概率定义为在这多次划分结果中，节点i和节点j划分入同一个社团的概率。节点成对概率pij计算公式为：

　　pij=∑Nn=1δn（Ci，Cj）/N（2）

　　式中，N为在同一个图上运行相同算法的次数；Ci和Cj分别为节点i和节点j所属社团编号。从公式（2）中，可以知道节点成对概率pij的取值在0到1之间。若pij为0，则表示在多个划分结果中，节点i和节点j一次都未被划分入同一个社团中；若pij为1，则表示节点i和节点j每次都被划分进同一个社团中。

　　2实验条件和数据