复杂网络半监督社区发现方法研究

Community detection is an important research hotspot of complex networks. Guiding the process of discovering communities with little prior knowledge is a novel paradigm of community detection, but most of the proposed algorithms have some limitations, such as neglecting contaminated noisy prior knowledge, high computation complexity .In response to these issues, this project studies the community detection based on graph-based semi-supervised learning theory, combining nodes labels with the topological structure. In order to make the pattern of label propagation more fits the task of community detection, this project analyzes the indexs of node similarity in complex network and proposes a method to construct the transfer weight matrix of nodes labels. To lower the interference of noisy labels, a method for identifying and revising noisy labels is developed based on strategies of correcting the marginal nodes labels and adding pseudo-label so that keep the balance of the number of labels of each community and filtering the wrong nodes labels. Besides, a category of near-linear time algorithms of semi-supervised community detection is presented to satisfy the demand of community identification in large-scale real networks, and the performance of the algorithms is tested and evaluated in large-scale real network. The research results not only can enrich the framework of community detection methods, but also possess wide application prospects in many diverse fields such as biology, sociology and economics.

社区发现是复杂网络的一个重要研究方向。利用少量先验知识指导社区识别是社区发现方法的一种新模式,但目前基于该模式的方法大多存在未处理噪音先验、计算开销大等问题。针对这些问题，本项目借鉴基于图的半监督学习理论，融合已知顶点标签和网络拓扑结构对社区发现方法进行研究：分析复杂网络顶点相似性度量指标，提出复杂网络顶点标签转移权重的构建方法，使标签传播行为模式适合社区发现任务；运用修正社区边缘顶点标签、增加伪标签使各社区内标签均衡以及过滤错误顶点标签等策略，提出噪音标签甄别和修正方法，从而降低噪音标签对社区发现算法的干扰；结合大规模网络社区发现的应用需求，提出一类时间复杂度为近线性的半监督社区发现算法，并对算法的性能在大规模真实网络中进行测试和验证。该研究不仅能丰富社区发现方法体系，而且在生物学、社会学以及经济学等诸多领域具有广阔的应用价值。

社区结构是复杂网络中的重要属性，在真实网络中普适存在。如何挖掘社区结构以及分析社区结构特性是近几年网络科学领域的研究重点。利用少量先验知识指导社区识别是提升社区识别精度的重要模式，但目前基于该模式的方法大多存在未处理噪音先验、计算开销大等问题。因此，对半监督社区发现方法以及社区结构特性的进行深入研究，具有重要的理论价值和现实意义。.本课题研究的重点是如何设计鲁棒并快速的半监督社区发现方法，并分析社区结构对网络的影响。需要研究并解决的主要问题有四个方面： 1）网络中社区个数的估计以及负向标签的处理方法；2）提出噪音标签甄别和修正方法，从而降低噪音标签对社区发现算法的干扰；3）提出一类时间复杂度为近线性的半监督社区发现算法；4）研究社区结构与重要性节点以及信息传播之间的关联特征。基于本项目的研究成果，已经在重要国际会议和期刊发表（已接受）9篇学术论文，其中SCI检索7篇；另外有3篇已投相关SCI期刊，状态为小修；申请发明专利1项；培养硕士研究生8名。