结点—链接协同划分的复杂网络重叠社团发现方法研究

Community detection in complex networks is of fundamental importance for comprehending network function and forecasting network activities, which has been used in many areas, such as terrorist organization recognition, social network analysis, etc. Especially, the detection of overlapping communities is the current research focus in this area. Recently, there are several types of overlapping community detection methods having been proposed. The link partitioning method, as the conceptually naturality, is a particularly promising class of techniques for this task, being actively researched and developed. However, this type of method tends to get highly overlapped communities, which is not well-suitable for networks with slightly overlapped community structures. For identifying the community structures with arbitrary varying degrees of overlaps, the proposal here attends to study the problem of overlapping community detection from the perspective of hybrid node-link partitioning. Our purpose is to develop a new class of method for the detection of overlapping communities by dividing a network into a hybrid node-link community structure, which consists of both node communities and link communities as its elements. This idea not only permits nodes to belong to multiple communities, but also does not force every link into a community. Thus, it can describe the community structures with arbitrary varying degrees of overlaps naturally, which includs both non-overlapping case and highly overlapping case as its special cases. Here we mainly focus on the research of hybrid node-link partitioning methods based on the probabilistic models, the content of which includes: 1) unified generative models describing node and link communities simultaneously; 2) learning algorithms of the above models for inferring the coexisted node and link communities; and 3) selection methods for determining the best hybrid node-link community structure from the candidate solusions.

复杂网络社团发现对理解网络功能、预测网络行为等有重要意义，被广泛应用于恐怖组织识别、社交网络分析等实际问题，重叠社团发现是其研究热点。目前已提出一些不同类型的重叠社团发现方法，其中2010年Nature上报道的链接划分思想，由于概念的自然性，被视为一类特别有前景的方法。然而这类方法仅适用于社团结构高度重叠的网络。针对"如何有效发现任意重叠程度之社团结构"这一难题，本项目拟从结点-链接协同划分的角度开展研究。通过将网络划分为由结点社团和链接社团共同组成的混合社团结构，开发一类新的重叠社团发现方法。该思路不仅允许结点同属于多个社团，而且不强制任何一条边都属于某个社团，因此可天然描述具有任意重叠程度的网络社团结构。本项目将重点研究基于统计模型的结点-链接协同划分方法，主要包括：1）同时刻画结点社团和链接社团的统一生成模型；2）统一生成模型的参数学习方法；3）最优结点-链接混合社团结构的选择策略。

复杂网络社团发现对理解网络功能、预测其行为等有重要意义，被广泛应用于舆情分析、电子商务等实际问题，重叠社团发现是其研究热点。目前已提出一些不同类型的重叠社团发现方法，其中2010年Nature上报道的链接划分思想，由于概念的自然性，被视为一类特别有前景的方法。然而这类方法仅适用于社团结构高度重叠的网络。.针对“如何有效发现任意重叠程度的社团结构”之难题，项目组从结点-链接协同划分的角度进行了研究。通过将网络划分为由结点社团和链接社团共同组成的混合社团结构，开发出一类新的重叠社团发现方法。该思路不仅允许结点同属于多个社团，而且不强制任何一条边都属于某个社团，可天然描述具有任意重叠程度的网络社团结构，有效解决了以上难题。.我们重点基于统计模型来研究结点-链接协同划分方法，主要包括：1）同时刻画结点社团和链接社团的统一生成模型；2）统一生成模型的参数学习方法；3）最优结点-链接混合社团结构的选择策略。我们还通过结合半监督、文本、动态等多模态信息进一步提升社团发现质量、标注社团语义，开展了一些有益的扩展工作。.项目组基于以上工作发表论文21篇，其中：CCF A类会议长文6篇，A类会议poster 1篇，C类会议长文1篇；JCR一区论文1篇，二区7篇，三区4篇；国家一级学报1篇（EI）；被IEEE Trans、IJCAI等国际知名杂志或会议多次引用和评价（google引用99次），在该领域产生了一定影响。譬如：我们提出的结点-链接协同划分思路，被美国匹斯堡大学同行Sánchez视为与链接社团发现、统计推断社团发现相并列的一类新方法；李德毅院士等基于我们文章中的非负矩阵分解方法设计其模型的求解算法；被美国海军研究实验室信息技术部门的Paxton等在Springer图书Advances in Information Security中视为4类社团发现方法中的一类代表工作。.我们将以上提出的方法成功用于大规模语音识别问题，发表于Interspeech-15；用其分析蛋白质交互网络，得到具有现实意义的蛋白质功能组；用其分析单词联想网络，得到具有深度语义相关性的单词类簇。具备良好的应用前景。