融合网络拓扑与结点、链接属性的重叠社区发现方法研究

Community detection is a fundamental task in the analysis of networked data, which had been used in many areas, such as social networks analysis and biological function prediction. Especially, overlapping community detection has attracted increasing attention and become the current research focus in this field. The traditional community detection methods just used network topology, which is the only information source and often contains noise. Recently, several works began to combine network topology with node attributes (or with link attributes) to discovery community structure. Actually, network topology, node attributes and link attributes are three different facets of the same problem. Furthermore, these three modalities of data are highly related and can complement with each other. Thus, combining all of the three types of information will be more powerful for discovering meaningful community structure in real life. While, it is really a challenge to effectively integrate these three types of information, which are generated from different perspectives, to identify community structure. In order to effectively integrate network topology, node attributes and link attributes for the detection of overlapping communities, we intend to carry out the following researches: 1) We first characterize coexist, correlated node community memberships and link community memberships by using network topology; 2) We then combine network topology with node attributes via node community memberships, and combine network topology with link attributes via link community memberships, so as to attain the coexist node community structure and link community structure which contain all of these three types of information; 3) At last, we infer the best overlapping community structure between the derived node community structure (with disjoint communities) and link community structure (with highly overlapped communities). The above idea not only can naturally combine network topology, node attributes and link attributes together to find community structure, but also provides a new way for overlapping community detection.

社区发现是网络型数据分析中的关键任务，被用于社会网分析、生物功能预测等诸多方面，重叠社区发现是其研究热点。传统社区发现仅依赖网络拓扑，信息源单一且常存在噪音。最近一些研究开始结合结点或链接属性发现社区结构，但实际上结点、链接属性和网络拓扑描述的是同一问题之不同侧面，三者相互关联、互为补充，故将其同时融合更有利于发现功能上具有现实意义的社区结构。但如何有效融合这三类源于不同视角的信息无疑具有挑战。针对“有效融合网络拓扑与结点、链接属性的重叠社区结构发现”难题，本项目拟：1）利用网络拓扑刻画关联对应的结点社区隶属关系和链接社区隶属关系；2）以结点社区关系融合结点属性、链接社区关系融合链接属性，得到综合三种信息的结点社区和链接社区结构；3）进而在无重叠的结点社区与高度重叠的链接社区之间推导最佳的重叠社区结构。该思路不仅可天然的有效融合网络拓扑与结点、链接属性，而且为重叠社区发现提供了一条新途径。

传统社区发现仅依赖网络拓扑，信息源单一且常存在噪音。最近一些研究开始结合结点或链接属性发现社区结构，但实际上结点、链接属性和网络拓扑描述的是同一问题之不同侧面，三者相互关联、互为补充，故将其同时融合更有利于发现功能上具有现实意义的社区结构。但如何有效融合这三类源于不同视角的信息无疑具有挑战。.针对“有效融合网络拓扑与结点、链接属性的重叠社区结构发现”难题，项目组：1）利用网络拓扑刻画关联对应的结点社区隶属关系和链接社区隶属关系；2）以结点社区关系融合结点属性、链接社区关系融合链接属性，得到综合三种信息的结点社区和链接社区结构；3）进而在无重叠的结点社区与高度重叠的链接社区之间推导最佳的重叠社区结构。该思路不仅可天然的有效融合网络拓扑与结点、链接属性，而且为重叠社区发现提供了一条新途径。此外，我们还通过融入半监督、动态、社区增益等信息，提升社区发现精度；同时对社区进行语义解释，实现社区画像；从而对项目进行了有益扩展。.项目组基于以上工作发表论文28篇，其中：CCF A类会议长文10篇，JCR三区以上期刊论文8篇。被国内外同行在ACM/IEEE Trans、AAAI、IJCAI等主要期刊或会议上多次引用和评价，具有一定的影响力。譬如：COMSATS 信息技术大学Muaz A. Niazi教授在其39页的综述中（2017.8发布于arxiv），按多种标准对全世界社区发现领域的学者进行分析和排名（在1991-2016时段内），在其基于“介数中心性”的排名中，项目负责人何东晓排名第4。方滨兴院士在其最新的文章中同时关注了我们5个工作，并将我们的UEOC选作对比算法。.最后，我们将以上提出的方法成功用于大规模Web服务计算问题，发表于ICWS-18，并申请了发明专利。新方法综合考虑了服务网络数据不同粒度及广义社区结构这两种特性，完成了对服务网络结构和服务语义两种信息的综合建模，从而提高了服务网络上社区发现的精度并具有良好的实用性。