秦丽娟   李慧   吴敏

摘  要  针对当前研究复杂网络社区发现的热点问题, 采用了一种基于极大团的聚类融合算法用于复杂网络社区发现. 该算法将聚类融合引入到极大团中, 利用极大团获得初始群体. 在初始群体的基础上, 采用Freeman的中心性判断节点在不同群体中的重要性, 通过洪泛聚类筛选出网络核心. 借鉴Newman快速算法中的层次聚类的思想并将网络模块性函数Q作为目标函数, 快速有效地对初始群体进行聚类. 在经典复杂网络及大规模复杂网络上对CDMCC算法进行测试, 并与当前具有代表性的社区探测算法进行比较, 实验结果表明CDMCC算法具有有效性与高效性. 

关键词  复杂网络, 社区发现, 网络聚类, 极大团

DOI    10. 3724

Community Detection Algorithm in Complex Networks Based Maximal Clique Clustering

QIN Li-Juan,  LI Hui,  WU Min

Department of Educational Technology, Capital Normal University, Beijing 100048 (E-mail: lihuicnu@163. com)

Abstract  Community detection has been the focus of many recent efforts on complex networks. In this paper, we adopt CDMCC algorithm based maximal clique for community mining in complex networks. The CDMCC introduces clustering combination into the maximal clique algorithm and gets cohesive subgroups by the maximal clique algorithm. The importance of nodes in different groups was judged by centrality of Freeman, and using flood clustering we get the core of networks. The CDMCC employs fast algorithm of Newman and network modularity Q as objective function and combines the subgroups with clustering algorithm. The CDMCC has been tested on both classical complex networks and the large-scale complex networks, and compared with some competitive community detection algorithm. Experimental result has shown that CDMCC is highly effective and efficient for discovering community structure. 

Key words  complex network, community detection, network clustering, maximal clique

现实世界中的复杂系统都以网络的形式呈现, 这些网络也都具有复杂网络的特性, 如生物系统中的新陈代谢网、蛋白质相互作用网、基因网、食物链网, 科学系统中的因特网、万维网、BBS网, 社会系统中的科学家协作网、电子邮件网等. 目前对复杂网络基本统计特性的研究吸引了众多研究者, 复杂网络分析已成为当前最重要的多学科交叉研究领域之一[1-4]. 研究者们通过对各类网络(如科技网、社会网、生物网等)的统计分析, 发现复杂网络中普遍存在着小世界(Small-world)特性[1]、无标度(Scale-free)特性[2]等基本统计特征. 

随着研究的深入, 复杂网络的另一特性——社区结构[3]也被广泛关注, 科学界出现了一股研究社区结构的热潮[5-21]. 根据应用领域的不同, 社区结构具有不同的内涵, 比如: 社会网络中的社区表示具有某些相似兴趣爱好的人物, 生物网络中的功能组揭示了具有相似功能的生物组织模块, Web网络中的文档类簇包含了大量具有相关主题的Web文档等[22]. 复杂网络社区结构的发现对于复杂网络的拓扑结构分析、功能分析和行为预测具有重要的理论意义和实用价值, 已被广泛应用于组织结构管理、识别、新陈代谢途径预测、蛋白质相互作用网络分析、Web社区挖掘、搜索引擎等诸多领域[3, 7, 12-13, 23]. 

2004年, Newman等人[24]提出了一个定量评价网络社区结构优劣的度量标准——网络模块性函数Q. 此后, 以Q函数为目标函数的组合优化方法成为探测网络社区结构的主流方法之一, 常见的算法有: GN(Girvan-newman)[3]、FN(Fast newman)[15]、SA(Simulated annealing)[6]、MSA(Modularity spectral algorithm)[25]、ITS(Iterated tabu search)[20]以及LPA(The label propagation algorithm)[12, 16]等. 由于最大化函数Q是NP完全的[11], 所以这些算法都是近似优化算法. 遗传算法(Genetic algorithm,  GA)可以有效解决NP难题, 但是基于GA的社区发现算法[16-19]寻优能力不强, 收敛速度慢. 此外, 这类算法还普遍采用随机生成的初始群体和随机地、无针对性地变异, 往往导致算法失效. 

与以往的社区划分算法不同, 本文不再对现有网络进行分割, 而是采用极大团算法[27]发现初始群体并对其进行聚类融合, 从而发现社区. 首先, 基于剪枝策略实现复杂网络社区极大团发现；然后, 根据极大团筛选网络的核心节点簇, 通过判断节点的Freeman中心性[26]分配节点到各核心节点簇从而生成初始群体；最后, 采用洪泛聚类, 将剩余节点加入到各社区中. 由于最终生成的社区比较琐碎, 因此借鉴Newman快速算法的层次聚类思想和模块度最优化思想, 在没有正直时的聚类结果为最优社区发现结果, 在社区合并过程中还记录了Q值的变化情况. 

1. 极大团发现算法MCA

社会网络分析学家通常使用凝聚子群[30, 31]的概念来描述一组社会关系联系非常紧密的群体. 凝聚子群内部的成员通常都倾向于具有类似的兴趣爱好、共同的信仰、近似的价值观以及行为方式等. 常见的凝聚子群包括学生会团体、球队、俱乐部、、犯罪帮派和宗教祭祀等. 基于凝聚子群本身所具有的这种实际应用背景, 研究了凝聚子群中最基本的一类模型——团结构(Clique)[32-34], 试图在实际复杂网络中能够高效地挖掘出所有潜在的极大团结构. 

1. 1  基本概念定义

复杂网络可以建模为无权无向图, 其中V表示网络的节点集合, E表示边的集合. 

定义1 给定无权无向图G, 对于任意子图, 如果, 那么子图被称作完备子图或团. 

定义2 如果不存在其他团使得, 则称为极大团(Maximal Clique). 

在图1中, {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, {0, 1, 2, 3}, {1, 2, 4}是6个团, 而{0, 1, 2, 3}及{1, 2, 4}是极大团, 因为团{0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}包含在{0, 1, 2, 3}中, 而{1, 2, 4}则不包含在任何比它更大的团中. 

极大团是给定网络中连接最为紧密的一组节点, 它代表了凝聚子群所期望具有的三大结构特点: 

(1) 认知度: 对于极大团里面的每个节点, 其余节点都是它的邻居, 代表了最为紧密的联系程度. 

(2) 可达性: 极大团具有最小的直径, 每个节点仅通过一跳即可到达结构中其余各点. 

(3) 健壮性: 由于极大团成员之间联系最为紧密, 随机去掉若干成员不会对系统剩余节点之间的通信造成严重破坏.

图1  极大团示例

1. 2  MCA算法实现

在给定图G中, 尽管理论上每条边是最简单的团(), 然而的团往往才具有真正的实际应用意义. 因此, MCA的基本思想是基于搜索三角形并配合一定的剪枝策略来枚举出所有的极大团(). 

搜索过程如下: 给定节点, 对于, 我们首先找到所有可能与、可以构成三角形的节点；然后从与出发, 进一步递归地从集合中找到所有可能的节点, 使得. 因为, 有, 所以节点、、及进一步构成了大小为4的团结构. 整个过程将依次递归进行, 直到再也没有搜索到任何的三角结构为止, 最终将得到一棵以节点为根的搜索树, 树中每一个内部节点分别与一个团结构相对应, 而叶子节点则代表了节点所处的所有可能的极大团结构. 极大团发现算法的基本流程如图2所示. 

对于给定节点, 每次从及相应的△集合中选择序号最小的节点开始, 这样形成的字典序可以有效地避免对同一个候选团结构的重复搜索. 比如, 整个搜索空间按照节点序号的字典序而有序地组织起来, 在每一棵搜索树中, 各个内部节点对应着递归搜索的每一阶段所扩展得到的团结构, 而所有叶子节点则代表了可能的极大团结构. 在图G中, 对于候选团结构, 根据定理l来判定是否为极大团. 

图2  MCA算法流程图

定理1 在给定图G中对于任意的候选团结构,是极大团当且仅当对于, 不存在节点使得. 

每当到达搜索树的叶子节点时, 根据定理 1来判别当前候选团是否为极大团. 但是定理1需要遍历集合中的所有节点, 当该集合规模很大时, 会对算法产生影响, 因此进一步使用第一个剪枝策略. 

剪枝规则1 对于候选团结构, 选择集合中度最小的节点来判定是否为极大. 

定理2 在候选团结构中, 对于, 都有. 

剪枝规则2 对于候选团结构, 选择度大于或者等于||的节点来进一步扩展. 

剪枝规则3 在某一给定的搜索树中, 如果当前团结构中的节点与所有可以扩展的节点共享相同的团标记, 那么停止扩展当前的团结构并递归返回. 

1. 3  性能分析

在理论上, 由于MCA算法的每一步是基于三角结构进行搜索, 并精确给出了图中的所有极大团, 因此它的时间复杂度与给定图中的所有极大团数目成正比, 即: O(C), C表示给定图G中所有极大团的数目. 

2.  基于极大团聚类的社区发现算法CDMCC(Community Detection Based Maximal Clique Clustering)

人们对极大团结构在不同方面进行扩展, 引入了凝聚子群中的其它结构定义, 包括:  k-core[34]、k-clan[35]、k-clique[36]、k-plex[37-39]以及准团[30, 40]等. 虽然它们在不同领域得到了广泛应用, 但是许多研究发现由于定义中变量k及的存在, 这些使得社区结构具有规律性. 这种结构上的制约使得算法只能得到数目众多但实际意义不大的琐碎小结构, 而这些小结构可能将原本具有实际意义的一般子结构分割破坏, 以至于掩盖了网络中真实的社区结构. 

在现实生活中, 社区结构反应的可能是具有相似主题的网页和文档、特定的消费群体以及某一领域的研究方向等. 因此, 自然地发现给定复杂网络中的社区结构是下面讨论的重点. 

2. 1  基本概念定义

定义3 对于给定图G中的任意节点, 定义为包含节点的所有极大团集合, 所有组成的集合表示为. 对于节点, 如果把它所处的极大团看成的一种社会关系, 由于包含了所有的社会关系, 我们称集合为节点的社会圈. 

定义4 对于任意, 如果(f是预先设定的阈值, 用来描述集合、之间的重叠程度), 则称集合包含于, 并表示为. 如果对于任意,都不包含于, 则称集合为图G的核心, 节点称为的中心. 

令集合K表示图G中所有核心的集合, 定义集合表示所有被集合K所覆盖的节点, 并令表示任意一对核心之间共有节点的并集. 

定义5 对于图G中任意节点及子图, Freeman中心性描述了在中的重要性并定义为: 

              (1)

定义6的内聚性[27]进一步定义为: 

(2)

描述了子图具有“星形”结构的趋势,越大, 这种趋势也就越强. 

2. 2  CDMCC算法实现过程

CDMCC算法的基本思想, 以相互重叠的极大团作为网络核心并对核心进行筛选；然后将剩余节点根据特定距离公式归并到相应的核心从而构造出网络的候选社区结构；最后将得到的候选社区结构进行适当合并调整, 从而得到一组可能的最优社区划分. 

2. 2. 1  筛选网络核心

对于任意两个节点, , 如果的社会圈涵盖了的全部社会圈, 称包含. 如果节点的社会圈不被自身以外的任何社会圈所包含, 说明内部的节点联系足够紧密并且具有足够的规模, 那么可以地成为给定图G的核心. 对于节点, 其社会圈的规模越大,成为核心的概率也越大. 因此, 在筛选核心时, 可以把集合C中的元素按照大小降序排列, 即,. 

网络核心筛选过程如下: 首先, 选取元素, 将所有被包含的其他元素, , 从集合C中删除. 然后, 对于集合C中的每一个剩余元素, 由于不能包含, 说明节点的社会圈不足以涵盖节点的社会圈, 因此如果在集合中存在少数极大团同时包含节点与, 就从中删除它们以避免重复. 过滤后的集合作为图G的核心加入到集合K中. 继续寻找集合C中下一个最大的元素, 采取同样的筛选过程, 把最终得到的加入到集合K中. 此过程反复进行, 直到集合C变为空集时停止. 网络核心筛选的流程如图3所示. 

图3  网络核心筛选流程图

2. 2. 2  在候选核心集合中去掉重复节点

由于得到的社区之间是彼此不重叠的, 所以集合K中的元素彼此之间没有公共节点. 对于每个节点, Freeman中心性描述了在给定子图中的重要性. 给定集合K中的任意核心, 其对应子图中节点的Freeman中心性越高, 说明在核心的重要性也就越明显. 因此, 使用节点的Freeman中心性来度量节点到相应网络核心的距离. 集合中的每个节点被指派到集合K中距离最近的网络核心. 在候选核心集合中去掉重复节点的流程如图4所示. 

图4  在候选核心集合中去掉重复节点流程图

2. 2. 3  洪泛聚类

在极大团发现算法中, 有很多节点不属于任何极大团, 所以当删除重复的网络核心后, 以集合K中的每个元素作为聚类中心, 采用“洪泛”的方式对剩余节点进行聚类, 并将其加入到各个核心中形成社区. 

聚类过程如下: 首先, 集合中的所有节点被标记为使用过的节点(old). 接下来, 所有距离中的节点为一跳且未被标记为old的节点, 即:,未被标记为old, 被指派到K中距离最近的核心. 然后, 集合中的每个元素被标记为old, 更新为, 使得中的元素为距离集合中的节点为一跳且没有被标记为old的节点, 将中的元素指派到K中距离最近的核心, 此过程迭代进行直到所有节点都被标记为old时停止. 洪泛聚类的流程如图5所示. 

图5  洪泛聚类流程图

2. 2. 4  局部调整初始社区结构

经过洪泛聚类, 更新过的集合K构成了给定图G的最初社区结构. 分析发现仍然存在一些非常琐碎的小社区, 但是真实生活中这种零星的小社区往往是不存在的. 

为了解决这一问题, 借鉴Newman快速算法的层次聚类思想[15], 从现有初始社区出发根据模块性的增量的变化进行局部贪心以优化网络. 每次迭代地合并能够使>0最大的两个候选社区结构直到停止. 每一次迭代都计算网络模块性Q值, 最终选取Q值最大时的社区发现结果输出. 假设初始社区结构的模块性为, 当合并社区i和j时, 合并所得的社区表示为(ij), 那么有: 

    (3)

其中,是连接社区i中所有节点的边数.是连接社区i中的节点到社区j中的节点的边占网络中所有边的比例. 

局部调整初始社区结构的流程如图6所示. 

图6  局部调整初始社区结构流程图

2. 3  性能分析

在实际网络中使用MCA算法枚举出所有极大团的时间复杂度为O(C), . 将图G中最大团的大小设为, 计算核心集合K的时间复杂度为；在集合K中去掉重复节点的时间复杂度为；由于集合K所能覆盖的节点数很少, 所以, 将剩余节点指派到距离最近的核心中的时间复杂度为, 而基于网络模块性的优化过程时间复杂度为. 在稀疏图中, , 所以CDMCC算法的整体时间复杂度近似为. 

3.  实验

本文基于空手道俱乐部网络 (Karate)、海豚网络 (dolphin) 、BBS兴趣网络 (Interest) 和大规模BBS回复网络 (Big) 四个数据集(网络参数见表1), 对于前三个数据集分别采用GN 算法和CDMCC 算法实现复杂网络社区发现, 最后一个数据集采用CDMCC 算法实现复杂网络社区发现, 并分析比较了两种算法的社区划分效果. 在这些数据集中, 不仅有包含几十个节点、几百条边的小规模网络,  像空手道俱乐部网络, 海豚网络以及兴趣网络都是这类网络；也有包含上千个节点、数万条边的大规模网络, 像BBS论坛数据集中的大规模网络就包含了上千个节点, 数万条边. 

表1  实验中用到的网络

空手道俱乐部网络 (Karate) 是 Zachary 通过对一个美国大学空手道俱乐部历时两年的观测而构建的社会网[28]. 它以俱乐部中的 34 个成员作为节点, 如果两个成员之间存在关系, 那么他们对应的节点之间就会有一条边相连. 由于俱乐部的经费问题, 教练和校长发生了冲突, 这个俱乐部后来为两个俱乐部, 他们分别以管理员和教练作为领导者. 该网络的真实社区结构如图 7(a) 所示: 黄色表示中心节点, 其中节点 1 代表俱乐部教练, 节点33 代表俱乐部的管理者；以该网络为例运行CDMCC算法, 发现24个极大团, 经过筛选得到5个核心, 最后通过聚类得到的结果包含两个社区, 如图 7(a) 所示. 图中三角形节点代表以节点33为中心的社区, 由拥护俱乐部管理者的人组成；菱形节点代表以节点1为中心的社区, 由人拥护校长的人组成. 可以看出, CDMCC算法探测出了 Karate 网络的真实社区结构. 以该网络为例运行GN算法, 在Q值最大时的到两个社区, 如图7(b)所示. 两个算得到的结果基本相同, 但是CDMCC算法复杂度远小于GN算法, 所以更优. 

图7  采用CDMCC和GN算法所得的Katate社区

3.2  海豚网络

海豚网络是 Lusseau 等通过对新西兰神奇湾中 62 个不同性别海豚的长时间观测而构建的动物社会网络[29]. 他们发现这些海豚的交往呈现出特定的模式. 每个海豚代表一个顶点, 如果两个海豚间关系密切, 那么它们对应的节点之间就会有一条边相连. 这些海豚被天然的分为雄性海豚组和雌性海豚组两个社区. 该网络的真实社区结构如图 8(a)所示. 以该网络为例运行CDMCC算法, 发现13个极大团, 经过筛选得到8个核心, 最终通过聚类得到的结果包含两个社区, 两个社区的节点分别用三角形和正方形表示, 如图8(a) 所示. 可以看出,  CDMCC算法正确地探测出了 Dolphin 网络的真实社区结构. 以该网络为例运行GN算法, 在Q值最大时的到四个社区, 如图8(b)所示. GN算法将其中一个社区细分为3个子社区, 分出的结果基本相同, 但是CDMCC算法复杂度远小于GN算法, 所以更优. 

(a)CDMCC对Dolphin的聚类结果

(b)  GN对Dolphin的划分结果

图8  采用CDMCC和GN算法所得的Dolphin社区

3.3  兴趣网络

兴趣网络(Interest)是通过下载BBS论坛数据集构建的兴趣网络, 如果回帖者对发帖者有回复, 那么他们对应的节点之间就会有一条边相连, 而且回复同一个发帖者的节点也会有连边(节点具有相同兴趣). 该网络的社区结构如图9(a)所示. 以该网络为例运行CDMCC算法, 发现25个极大团, 经过筛选得到6个核心, 最终通过聚类得到的结果包含5个社区, 使用5种形状的节点表示5个社区, 如图9(a)所示. CDMCC算法正确地探测出了 Interest 网络的真实社区结构, 热帖就是一个社区. 以该网络为例运行GN算法, 在Q值最大时的到五个社区, 如图9(b)所示. GN算法与CDMCC算法分出的结果基本相同, 但是CDMCC算法复杂度远小于GN算法, 所以更优. 

(a)  CDMCC对Interest的聚类结果

(b)  GN对Interest的划分结果

图9  采用CDMCC和GN算法所得的Interest社区

3.4  大规模 BBS 网络

大规模网络(Big)是直接采用下载的BBS论坛数据集构建的网络, 如果回帖者对发帖者有回复, 那么他们对应的节点之间就会有一条边相连, 运行CDMCC算法, 发现262个极大团, 经过筛选得到17个核心, 最终通过聚类得到的结果包含5个社区. 由于GN算法的算法复杂度较高, 所以对于大规模的数据集, GN算法无法在短时间内实现社区划分. 由于网络规模很大, 所以没有给出图示. 

3.5  总结

GN算法采取的是删边的策略, 不断删除边介数最大的边, 从而得到社区划分. CDMCC算法采取的是聚类的方式, 将具有类似特征值的节点聚类从而发现社区, 与GN算法相比, CDMCC算法复杂度低很多, 所得社区结构也基本符合真实情况. 在GN算法中, 将Q值作为衡量社区划分结果的指标, 但是我们认为Q值并不能作为社区结构优劣的唯一指标, 可以将Q作为目标函数, 但是有时当Q值最大时, 并非最佳社区结构, 与真实情况有一定差距. 本文中, 我们综合考虑Q值和聚类过程中的社区变化情况, 最终取Q值相对较大且社区数目合理的情况作为最优社区结构. 

4.  结论

本文在极大团发现的基础上获得初始群体, 以Q函数作为目标函数, 采用洪泛聚类的方法将节点聚类到各自社区中. 实验表明, CDMCC算法具有收敛速度快、搜索能力强的特点, 对于包含上千个节点、数万条边的大规模复杂网络人能够较快的获得高质量聚类结果. 

将CDMCC算法与经典网络社区划分算法GN进行比较. GN算法是通过反复地计算边介数(Edge betweenness)、识别社区间连接和删除社区间连接, 以自顶向下的方式建立一颗层次聚类树, 从而划分网络社区结构. 该算法具有很高的时间复杂度, 只适合处理包含几百个节点的中小规模复杂网络. 而CDMCC算法与GN算法不同, 它是以网络模块性函数Q作为目标函数, 通过极大团来发现网络社区结构, 时间复杂度为. CDMCC算法的时间复杂度远小于GN算法的时间复杂度. 实验结果表明CDMCC算法的聚类质量和运行效率都要明显优于GN算法. 

下一步的工作主要是采用欧式距离函数替代模块性函数Q作为目标函数, 以期得到好的聚类效果. 

Reference

1Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks. Nature, 1998, 393(6638): 440−442

2Adamic L A, Huberman B A, Barabasi A L, Albert R, Jeong H, Bianconi G. Power-law distribution of the world wide web. Science, 2000, 287(5461): 2115a

3Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of National Academy of Sciences of the United States of America, 2002, 99(12): 7821−7826

4Yan G, Chen G, Lv J, Fu Z Q. Synchronization performance of complex oscillator networks. Physical Review E, 2009, 80(5): 056116

5Li J, Cheung W K, Liu J M, Li C H. On discovering community trends in social networks. In: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology. Washington D.C., USA: IEEE, 2009. 230−237

6Guimerà R, Amaral L A N. Functional cartography of complex metabolic networks. Nature, 2005, 433(7028): 5−900

7Palla G, Derényi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814−818

8Hu Y Q, Li M H, Zhang P, Fan Y, Di Z R. Community detection by signaling on complex networks. Physical Review E, 2008, 78(1): 016115

9Palla G, Barabási A L, Vicsek T. Quantifying social group evolution. Nature, 2007, 446(7136): 6−667

10Yang Bo, Liu Da-You, Liu Ji-Ming, Jin Di, Ma Hai-Bin. Complex network clustering algorithms. Journal of Software, 2009, 20(1): 54−66

(杨博, 刘大有, Liu Jiming, 金弟, 马海宾. 复杂网络聚类方法. 软件学报, 2009, 20(1): 54−66)

11Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007, 76(3): 036106

12Barber M J, Clark J W. Detecting network communities by propagating labels under constraints. Physical Review E, 2009, 80(2): 026129

13Leung I X Y, Hui P, Liò P, Crowcroft J. Towards real-time community detection in large networks. Physical Review E, 2009, 79(6): 066107

14Zhang Y Z, Wang J Y, Wang Y, Zhou L Z. Parallel community detection on large networks with propinquity dynamics. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France: ACM, 2009. 997−1006

15Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6): 066133

16Liu X, Li D Y, Wang S L, Tao Z W. Effective algorithm for detecting community structure in complex networks based on GA and clustering. In: Proceedings of the 7th In ternational Conference on Computational Science. Beijing, China: Springer, 2007. 657−6

17Gog A, Dumitrescu D, Hirsbrunner B. Community detection in complex networks using collaborative evolutionary algorithms. In: Proceedings of the 9th European Conference on Artificial Life. Lisbon, Portugal: Springer, 2007. 886−4

18Tasgin M, Herdagdelen A, Bingol H. Community detection in complex networks using genetic algorithms [Online], available: http://arxiv.org/abs/0711.0491, January 8, 2010

19Pizzuti C. GA-net: a genetic algorithm for community detection in social networks. In: Proceedings of the 10th International Conference on Parallel Problem Solving from Nature. Dortmund, Germany: Springer, 2008. 1081−1090

20Lü Z P, Huang W Q. Iterated tabu search for identifying community structure in complex networks. Physical Review E, 2009, 80(2): 026130

21Jin D, Liu D Y, Yang B, Liu J. Fast complex network clustering algorithm using agents. In: Proceedings of the 8th IEEE International Conference on Dependable, Autonomic and Secure Computing. Chengdu, China: IEEE, 2009. 615−619

22Fortunato S. Community detection in graphs. Physics Reports, 2010, 486(3−5): 75−174

23Porter M A, Onnela J P, Mucha P J. Communities in networks. Notices of the American Mathematical Society, 2009, 56(9): 1082−1097, 11−1166

24Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113

25Newman M E J. Modularity and community structure in networks. Proceedings of National Academy of Sciences of the United States of America, 2006, 103(23): 8577−8582

26Freeman L C. Centrality in Social Networks Conceptual Clarification. Social Networks, 1978, 1(79): 215-239

27Du Nan. Community structures and generative models of complex networks [Ph.D. Dissertation], Beijing University of Posts and Telecommunications, 2009

28Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4): 452-473

29Lusseau D. The emergent properties of a dolphin social network. Proceedings of the Royal Society B: Biological Sciences, 2003, 270(S2): 186−188

30Wasserman, S., K. Faust. Social Network Analysis. Cambridge: Cambridge University Press, 1994.

31Scott J. Social Network Analysis: A Handbook 2nd Edition.  London: Sage, 2000.

32Luce R, Perry A D. A method of matrix analysis of group structure. Psychmetrika, 1949, 14(2): 95-116

33Alba R. A graph-theoretic definition of a sociometric clique. Journal of Mathematical Sociology, 1973, 3(1): 113-126

34Freeman L C. The sociological concept of 'group': Anempirical test of two models. American Journal of Sociology, 1992, 98(1): 152-166

35Mokken R J. Cliques, clubs and clans. Quality and Quantity, 1979,  13(2): 161-173

36Luce R. Connectivity and generalized cliques in sociometric group structure. Psyehometrika, 1950, 15(2): 169-190

37Seidman S B. A graph theoretic generalization of the clique concept. Joumal of Mathematical Sociology, 1978, 6(1):139-154

38Balasundaram B. Clique Relaxations in Social Network Analysis: The Maximum k-plex Problem[Online], available: http://iem.okstate.edu/baski/files/kplex4web--ext.pdf, April 22, 2012

39Wu Bin, Pei Xin. A Parallel Algorithm for Enumerating All the Maximal k-Plexes. In: Emerging Technologies in Knowledge Discovery and Data Mining. Nanjing, China: Springer, 2007. 476-483

40Zeng Zhi-Ping, Wang Jian-Yong, Zhou Li-Zhu, Karypis G. Coherent closed quasi-clique discovery from large dense graph databases. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. Philadelphia, USA: IEEE, 2006. 797-802下载本文