复杂条件社区发现关键技术研究

The research on social networks gets more and more attentions due to the popularity of online social networks these years. Also, the role and importance of communities in social networks attracts attention of more and more people. However, research results in this field are far from satisfying people’s needs for real applications. This project aims to propose and study the problem of community detection with complex conditions in social networks. 1) Collect and analyze the collection of conditions and constraints on communities, and then formalize the problem of community detection with complex conditions based on second-order logic and set up the theoretical foundations. 2) Effectively reduce the cost of local community detection via the equivalent change of Boolean expressions, and fast detect global communities through semantic enhancement general architecture for community detection. 3) For in-complete social networks, detect global communities by the policies of topology improvement and deep learning, and restore the regional social network by the graph refining techniques and the Edeg2Vec method. 4) For large-scale dynamic social networks, discover communities with complex conditions based on the MR-BSP computational framework as well as the batch/incremental methods. It is the problem of community detection with complex conditions in social networks that has important theoretical significance and practical value. The research results of this project are expected to be widely used in many fields, such as character background investigation and community diversity analysis.

近年来在线社交网络的普及使得社会网络的研究越来越受到关注，社区在社会网络中的作用和重要性也吸引越来越多人的注意。然而该领域目前的研究成果尚不能满足现实中的应用需求。本项目旨在提出并研究复杂条件社区发现问题。在整理分析社区各类条件和约束的基础上，建立基于二阶逻辑的复杂条件社区发现问题的形式化描述与理论基础；通过布尔表达式的等价变换有效减小局部社区发现的计算开销，通过语义增强的通用社区发现框架实现全局社区的快速发现；针对不完全社会网络，通过拓扑完善策略和深度学习策略尝试实现全局社区的有效发现，通过图细化技术和Edge2Vec方法支持局部社会网络较为完整的修复；针对大规模动态社会网络，基于MR-BSP计算框架和批量/增量方法有效进行复杂条件社区发现。社会网络中复杂条件社区发现问题具有重要的理论研究意义和实际应用价值，本项目的研究成果可望广泛应用于人物背景调查、社团多样性分析等领域。

本项目旨在提出并研究复杂条件社区发现问题。通过4年的研究工作，课题组在VLDB Journal、IEEE TKDE、ACM TKDD、PVLDB、ICDE、KDD、AAAI和《软件学报》等国内外重要期刊和会议上发表论文32篇。这些论文包括SCI论文9篇、EI论文26篇、CCF A类长文11篇，申请国家发明专利4项、软件著作权3项，获得国际会议最佳论文奖1项和国内会议优秀学生论文奖 1项。.课题组广泛调研了国内外社区发现已有方法，针对现有方法没有深入考虑社区发现上下文的复杂状况这一不足，凝练提出复杂条件社区发现系列研究问题。通过布尔表达式形式化刻画具体的社区搜索条件，设计了一个解决条件社区搜索问题的通用框架，并提出三种“社区搜索+过滤”具体方法；提出禁止节点感知的社区搜索问题和对应方法，包括面向不同社区结构定义的若干变体；通过引入节点到查询节点的距离因素，提出了社区聚焦问题及对应方法FLCF，提升了发现的结果社区与查询节点的相关性；提出一种基于多标签传播的社区发现算法NMLPA，将节点属性转化为边权重加以利用。课题组还提出了一种基于种子聚焦的自适应关系发现方法OPT-A-RDFS，能够解决社区发现过程中给定的种子节点可能彼此不相关的的难题；重点研究了时序网络中的社区搜索方法，提出了短时社区搜索这一新问题，并提出对应方法 ShrimeCS，体现了社区的短时特性；提出了时间-拓扑分析的新思想，并给出T-cohesiveness的概念用以在时间和拓扑两个维度同时刻画时序子图的紧密度，并进一步提出时序图演化追踪与稠密子图查询两种时序图分析方法。.为方便社区发现和社区搜索技术的检验与比较，提出了一种高效且泛用的社交图生成器FastSGG。为支撑社区发现技术，针对网络中社会关系方向性的确定问题提出了DeepDirect方法；针对现有网络嵌入技术无法应对类别标签信息完全缺失的情况，提出了一种浅层方法RSDNE和一种新型图神经网络方法RECT以学习节点表示；针对现有节点特征表达方法缺少对跨图学习关注的情况，设计出一个包含消息路由对齐和消息聚合对齐两种策略的跨图表示学习解决框架；针对多重异构网络中的节点表示学习，提出了一个具有混合聚合流和分层注意力机制的端到端GNN模型HybridGNN。