一种基于中心极大团扩展的社区挖掘算法

Community mining algorithm based on central maximal-clique expansion

社区挖掘是复杂网络分析中的一项重要工作,目前已提出多种社区挖掘算法,但多数算法是通过节点间的连接关系来发现内聚的社区结构。结合真实网络中的节点具有不同的行为和影响力,在充分考虑网络中节点的连接关系的基础上,提出一种基于中心极大团扩展的社区挖掘两阶段算法。第一阶段发现初始社区:首先找到网络中所有的内聚子团,然后找出k个分散、内聚且有影响力的中心极大团作为初始社区;第二阶段形成最终社区划分:对初始社区外节点,充分考虑不同邻居节点对其潜在的影响力,采用局部模块度扩展的方法将节点扩展到与其连接紧密的社区内。实验结果表明,该方法能够快速揭示出网络中的社区结构,相比FN算法,具有较高的准确度和模块度,相比GN算法,不需要预先知道社区个数。

Community mining is an important work in complex network analysis,and many algorithms have been proposed.However,most of them are based on the links to find the cohesive community structure.Taking the nodes that have differentbehaviors and influences in real-world networks into consideration,together with links between nodes,a two-stagecommunity mining algorithm based on central maximal-clique expansion is proposed.In the first stage,initial communitiesare found:Firstly,all the cohesive cliques are found out in the network,and then k separate cohesive and influentialcentral maximal-cliques are chosen to form initial communities.In the second stage,the final community division isdetected:For the nodes outside the initial communities,taking potential impacts of neighbor nodes into consideration,theneighbor nodes are expanded to the corresponding connected closely community by adopting the local modularity.Experimental results show that the method can quickly reveal cohesive community structure in network,compared withthe FN algorithm it has a relatively higher accuracy and modularity,compared with the GN algorithm,it do not need toknow the prior number of communities.