半指导的核聚类检测网络社团方法

Kernel approach for detecting communities in complex networks based on semi-supervised clustering

近年来,复杂网络中的社团发现越来越受到研究人员的关注并且许多方法被提了出来。在这种背景下,最近李等人提出了一种用来评估社团质量的函数,称之为模块密度函数(即D值)。该函数显示了较高的D值对应于较好的社团结构,然而,优化该函数是一个NP难问题。通过模块密度函数D的半指导聚类优化,论证了模块密度函数的半指导聚类与核k方法的等价性并提出了一种新的半指导核聚类检测复杂网络社团方法。在一个经典的计算机产生的随机网络中检验了该算法,并与基于模块密度的直接核方法做了比较。特别地,当网络中社团结构变得模糊时,实验结果显示这种新的算法在发现复杂网络社团上是有效的。

In recent years,the problem of community structure detection has attracted more and more attention and many approaches have been proposed.In this context,Li et al recently propose modularity density objective function for community detecting called the D function.Empirically,higher values of the D function have been shown to correlate well with good community structures.However,optimization of the function is a NP-hard problem.In this paper,how to optimize the D function can be formulated as a semi-supervised approach problem.The equivalence of the semi-supervised and the kernel k-means based on modularity density are also proved and a new semi-supervised kernel clustering approach is proposed.The approach is illustrated and compared with direct kernel approach based on modularity density by using a classic computer generated networks.Experimental results show the significance of the proposed approach,particularly,in the cases when community structure is obscure.