基于灰色方法的社交网络群体识别问题研究

The rapid development of the social networks has been attracting the attention of more and more scholars. However, the social networks possess many spectific characteristics like extremely large scale, overlapping, multi-level structures, multiple relations, dynamicity, etc, some of which are lacked in the general complex networks. The specifities present great challenges to the community detection in the social networks. In this research project, guided by the grey system theory and based on the grey methods, we try to build grey models for the social networks with overlapping, multi-level and other complex structures and dynamic social networks with multiple uncertainty methods including statistics methods, fuzzy methods, etc. Then, efficient algorithms with strong robustness and high scalibility are developed through introducing the evolutionary computation methods and parallel computing frameworks. The performance of the algorithms are evaluated by theoretical analysis and simulated experiments. In theory, the results of the research will provide beneficial complement to the existing complex network clustering methods from a new perspective and boost the application of grey system theory and grey methods in new disciplines and realms. In pratice, the research results are important to the promotion of the development of the social and economic activities based on social networks, the discovery and prevention of the crime on social networks and the safeguard of the state security.

社交网络在世界范围内的飞速发展正引起越来越多学者的关注，由于其具有超大规模性、重叠性、层次性、多重性、动态性等不同于一般复杂网络的特性，使社交网络中的群体识别面临许多挑战。本研究拟在灰色系统理论的指导下，以灰色方法为主要工具，通过与包括概率统计方法、模糊方法等在内的多种不确定方法相结合，建立具有重叠、层次等复杂结构的社交网络、动态社交网络及具有复杂结构的动态社交网络的灰色模型。同时，引入进化计算方法及并行计算框架，设计具有强鲁棒性、高扩展性及可并行化的高效算法，通过理论研究与仿真实验相结合的方式对算法的性能展开评价与分析。研究的成果将在理论上从新的角度为复杂网络聚类方法提供有益补充，同时拓展灰色系统理论及灰色方法在新的学科领域的应用，在实践上对促进基于社交网络的新型社会、经济活动的发展、识别与预防基于社交网络的犯罪行为、维护国家安全等都具有重要的现实意义。

社交网络的超大规模性、重叠性、层次性、动态性等社交网络独有特性使社交网络中的社交群体发现研究面临挑战。目前，关于动态社交网络中的群体识别方面的研究c，其模型、算法及标准测试集的设计等还有很大的发展空间。因此，在社交网络对人们的日常生活及社会安全正在产生越来越大影响的背景下，应用灰色方法在处理不确定数据方面的优势，并与其它方法有效结合，对在社交网络中的群体识别问题展开研究，不但在学术研究上具有重要的意义，也具有较高的应用价值。.本课题针对复杂社交网络中的群体识别问题展开一系列研究。首先，研究了灰色方法在社区发现中的应用，提出了基于改进灰关联度与局部近邻传播的社区发现算法，基于灰关联分析的模糊聚类算法，基于灰关联分析的谱聚类算法。研究了边不完整的社交网络中的社区发现问题，提出了同时考虑网络拓扑结构与节点属性的社区发现算法。研究了社交圈子识别问题，提出了基于局部社区探测的社交圈子自动识别算法。研究了标签传播算法，提出了基于标签影响力的社区发现算法。研究了数据流上的隐私保护问题，提出了基于聚类的数据流匿名算法。研究了k匿名模型改进问题，提出了(k,g)匿名算法。其次，研究了重叠层次社区发现问题，提出了基于增广边簇序列的边社区发现算法，以及基于谱聚类的重叠层次社区发现算法。研究了基于MapReduce模型的并行社区发现问题，提出了基于局部/全局信息传播的社区发现算法，以及基于多标签传播的并行重叠社区发现算法。最后，研究了动态社区发现问题，提出了一种基于邻域跟随关系的社区表示模型Follow-Community，以及基于该模型的具有线性时间复杂度的邻域跟随算法，并进一步扩展得到用于动态社区发现的增量邻域跟随算法。基于MapReduce模型，提出了一种将标签传播算法和增量相关节点相结合进行社区发现的方法。.项目的研究成果一方面是对复杂网络中群体识别研究技术与方法的有益补充与完善，另一方面也为在基于社交群体发现与跟踪的电子商务、在线广告、安全监控等应用提供技术支撑。