随着在线社交网络的应用范围不断扩大，其已成为目前产业界和学术界的研究热点.社交网络成员之间依据社交关联形成了复杂的网络结构.对社交网络结构和动力学的分析，例如社团发现^[1]、链接预测^[2]、传播建模等^{[3, 4]}，具有重要的应用价值.

然而，急剧增加的网络规模，给网络结构分析带来了巨大挑战.例如，截止到2012年12月，Facebook在全球的用户节点总量已经超过10亿，Twitter的节点数也超过了5亿.现有的社团分析算法的复杂度多为O(n²)或O(n³)，只能用于分析中等规模(十万或百万节点级别)的网络.现有的解决方法是寻找快速算法^[5]，或者采用新的图计算框架，例如google的Pregel^[6].但是对于超大规模复杂网络，当前仍然没有高效的解决方法.

社团结构是社会网络中普遍存在的结构之一.人们通过社会关联形成若干社会团体，社团间的连边比较稀疏，社团内部的连边比较紧密.社团发现的目的是找出网络中密切交互的模块化子网，对更准确地理解复杂系统的组织原则、拓扑结构与动力学特性，具有十分重要的意义.

目前已有很多针对复杂网络的社团发现算法.GN算法^[7]是一种自顶向下的分裂方法，其基本思想是不断地从网络中移除介数最大的边，直到网络中每个节点就是一个退化的社团为止.在GN算法的基础上，Newman等^[8]提出了基于模块度优化的快速算法，克服了传统的GN算法只能处理中等规模网络的缺点，可以用于分析大型复杂网络.Ahn等^[9]提出了一种从边的角度出发，同时考虑社团结构的层次性和重叠性的单链接层次聚类算法，把一个社团看作一组有密切相关的链接集，而不是假设一个社团是一个节点之间有许多链接的节点集.

上述社团结构方法，都有一个共同点，即需要知道整个社团的网络拓扑结构.然而，有时只关心网络中的某个特定社团，例如，个性化营销希望找到与产品相符合的潜在用户群；舆情分析希望了解特定人群对某一话题的看法.在这种应用场景下，只需要找到关注的社团，而没必要给出网络中全部的社团结构.

本文提出了一种用于超大规模社交网络的社团抽取方法.与传统的社团发现不同，该方法是寻找网络中某个特定社团，而不是全部的社团结构.因此，不要求已知网络的全部拓扑结构，而是边爬行获取网络结构，边抽取社团，这会显著地提高算法在超大规模网络上的执行效率.算法的一个基本动机是，社团内部的连接比较紧密，而社团之间的连接相对稀疏.那么，从若干少量已知的社团内部节点出发，进行启发式的搜索，将连接紧密的邻居加入社团内部，将连接稀疏的邻居排除在社团外，这样就可以获得某个期望的特定社团的范围和结构.

考虑网络G，社团抽取的目标是找出网络G中一个已知规模的特定社团，假设网络全局拓扑的信息是未知的(即网络中节点和边的数量是未知的).

算法的基本思路是，从某些节点出发，沿着边扩展子图，从而不断扩大社团.在扩展的过程中，根据社团的性质，同时进行节点的筛选.因此，需要解决几个问题：1)起始节点的选取；2)社团评价的标准；3)节点的评价.社会网络上的节点，一般具有若干基本属性，可以用于标识其所属社团.如某用户的学校为“东北大学”，可以判定其属于东北大学社团.但是，一般只有少数节点具有明确的社团标签.本文视这些节点为核心种子节点，从这些节点进行扩展，找到属于该社团的其他节点.

对于社团的期望规模，根据经验选择社团的实际大小，例如在判定“东北大学”社团的过程中，选择东北大学的总人数作为社团的期望规模.对于社团的评价，一种通用的标准是社团内部关联紧密，外部关联稀疏.因此，通过社团内外连边的比值，可以有效地度量社团的“内聚”程度.如果在社团中加入一个节点使得社团的“内聚”程度增加，那么该节点属于社团的可能性较大，反之较小.因此，可以将社团抽取的过程视为从若干已知核心点出发的搜索过程，通过扩展当前社团中的节点，即将当前社团中节点的邻居节点作为被筛选节点，将属于社团内部的节点加入社团，筛掉不属于社团的节点，直到得到期望的社团规模为止.

根据以上思路，本文将社团抽取视为在隐含网络G上的搜索过程，目标是使搜索图的适应度函数最大化.一个子图的社团性质是否明显，取决于其内部关联是否大于外部关联.因此，定义评价子图的适应度函数为

另一个需要考虑的问题是如何选取初始节点.对于一个节点来说，当其连边大多都在社团G内部时，其属于社团的概率较大；当节点大部分的连边都指向社团外部节点时，其有很大可能不属于社团.因此，本文定义节点n的评价函数h为

基于以上两个函数，社团抽取算法主要包括两个过程：一个是寻找最有可能属于社团的节点，扩展该节点从而扩大子图；另一个是判断是否将该节点加入子图，这是通过判定加入该节点是否能增加子图适应度函数来决定的.重复上述步骤直到子图达到指定规模N为止，具体算法步骤如下:

1) 令初始节点集为S，初始社团G={S}；令社团期望规模为N；

2) While Size(G)＜N do;

3) 计算f_G及G中所有节点的h值;

4) 令G中h值最大的节点为n;

5) 令节点n的不在G中的邻居节点集为M;

6) selected=true;

7) While selected and Size(M)>0 do;

8) 令M中h值最大节点为m，M=M-{m};

9) 令G’=G+{m}，计算f_G’;

10) If f_G’>f_G;

11) then G=G’, selected=false;
12) End If;

13) End while;

14)End while.

算法中初始节点集可以由节点的社会标签确定，社团期望规模N一般通过经验判定.算法首先寻找社团G中最可能扩展的节点n，然后选择其中评价函数h值最大的节点加入社团G，重复上述步骤直到达到指定规模为止.

为了验证社团抽取算法的有效性，本文选用具有社团结构的仿真网络^[10]进行实验.每一个仿真网络包含4个子社团，每个社团的节点数均为n/4.对于网络中任意节点对，以一定的概率来放置一条连边.如果节点对在同一个社团内，则连边概率为p_in，否则为p_out.该方法可以生成具有明显社团结构的大规模网络，目前已成为社团发现算法的标准测试集^[11].

通常，具有明显社团特性的网络社团内部连边紧密，社团之间连边稀疏.为了保证仿真网络具有明显社团特性，本文取p_in>p_out.设一个节点的社团内连边数l_in=n · p_in/4，社团间连边数为l_out=3n · p_out/4，则有网络平均度(average degree)为 d_ave=l_in+l_out.图 1给出了3个平均度为12的仿真网络.其中图 1a中l_in=11，图 1b中l_in=10，图 1c中l_in=9，对应模块度分别为0.667,0.577,0.502.模块度越大，网络具有的社团结构越明显.本文所采用的仿真网络数据如表 1所示.

图 1(Figure 1)

Fig. 1

图1 四社团随机网络的拓扑示意图 Fig. 1 The topological diagram of ER-network with four communities (a)—lin=11 ； (b)—lin=10； (c)—lin=9.

表1

Table 1

表1(Table 1)

表1 四社团随机网络 Table 1 ER-network with four communities 名称 节点 边 模块度 pin pout Net1 1000 5945 0.667 0.02200 0.000670 Net2 1000 5944 0.577 0.02030 0.001300 Net3 1000 5995 0.502 0.01800 0.002000 Net4 1000 7990 0.495 0.02400 0.002700 Net5 1000 10131 0.518 0.03000 0.003300 Net6 1000 11999 0.499 0.03600 0.004000 Net7 1000 13984 0.500 0.04200 0.004700 Net8 1000 6201 0.413 0.01600 0.002700 Net9 20000 51946 0.601 0.00040 0.000040 Net10 40000 104209 0.630 0.00020 0.000020 Net11 60000 151276 0.599 0.00013 0.000013 Net12 80000 207524 0.605 0.00010 0.000010

表1 四社团随机网络 Table 1 ER-network with four communities

首先，分析算法准确度的影响因素.将社团抽取准确率定义为A=|N_extract∪N|/|N|，其中N_extract为社团抽取算法得到的点集，N为目标社团的点集.选取模块度相近但平均度不同的5个网络Net5~ Net9，分别从每个网络中随机选取100组个数为1~9的初始节点集合，取100组社团抽取结果的均值，结果如图 2所示.结果表明，初始节点的个数对社团抽取准确率的影响不大，这是因为本文所提出的社团抽取方法是从某些节点开始，对网络进行逐步搜索的过程.同时，对于不同平均度的网络，平均度越大，其抽取准确率越高.原因是对于平均度较大的网络，每一次进行网络搜索时，都可以有更多的社团内节点被找到.

图 2(Figure 2)

Fig. 2

图2 算法准确率的影响因素分析 Fig. 2 Analysis for the influence factors of algorithm accuracy

其次，本文分析了具有不同社团结构的网络上社团抽取算法准确率的变化.图 3给出具有不同模块度的网络Net1，Net2，Net3，Net8上社团抽取算法的结果.当模块度较高，即社团结构较明显时，社团抽取算法可以准确地得到网络的目标社团；当模块度较低时，社团抽取准确率仍然可以达到75 % 以上，验证了该算法的可行性.与基于模块度优化的社团发现算法^[8]相比，在具有明显社团结构的网络上，社团抽取算法达到了与社团发现相当的准确率.

图 3(Figure 3)

Fig. 3

图3 社团抽取算法与模块度优化算法的准确率 Fig. 3 The accuracy of community extraction algorithm and modularity optimal algorithm

最后，为了验证社团抽取算法的效率，选用经典的Newman模块度优化算法^[8]进行对比实验，图 4给出了两种方法在Net9~Net12上运行时间的对比结果.可以看出，在运行时间方面，社团抽取算法明显优于模块度优化算法.原因是社团发现算法考虑全局拓扑，得到整个网络的社团划分结果；而社团抽取算法考虑局部社团，通过节点扩展抽取网络局部，因此其效率较高.

图 4(Figure 4)

Fig. 4

图4 社团抽取算法与模块度优化算法的效率比较 Fig. 4 Comparison between community extraction algorithm and modularity optimal algorithm

本文分析了社交网络分析的社团发现需求，提出了社团抽取问题，并为大规模网络上的社团抽取问题提出了一个高效算法.

社团作为社交网络的基本结构特征，在网络分析领域具有重要的意义.社交网络上的个人行为与其所在社团具有紧密联系.因此，给出某节点所处的社团结构，具有重要意义.此外，社团抽取算法也可用于社团发现问题.如果已知网络中各社团的初始节点，那么就从网络的各个社团同时进行社团抽取.

下一步的工作将探索社团抽取算法在社团发现问题上的应用，同时进一步提高社团抽取算法的性能和准确度.