基于矢量影响力聚类系数的高效有向网络社团划分算法

来源：电子与信息学报杂志2017年第9期北京时间：

作者：邓小龙, 翟佳羽, 尹栾玉

单位：1.(北京邮电大学网络空间安全学院可信分布式计算与服务教育部重点实验室 北京 100876) ②(北京邮电大学国际学院 北京 100876) ③(北京师范大学社会管理研究院 北京 100875)

摘要：社团结构划分对于分析复杂网络的统计特性非常重要，以往研究往往侧重对无向网络的社团结构挖掘，对新兴的微信朋友圈网络、微博关注网络等涉及较少，并且缺乏高效的划分工具。为解决传统社团划分算法在大规模有向社交网络上无精确划分模拟模型，算法运行效率低，精度偏差大的问题。该文从构成社团结构最基础的三角形极大团展开数学推导，对网络节点的局部信息传递过程进行建模，并引入概率图有向矢量计算理论，对有向社交网络中具有较大信息传递增益的节点从数学基础创造性地构建了有向传递增益系数(Information Transfer Gain, ITG)。该文以此构建了新的有向社团结构划分效果的目标函数，提出了新型有向网络社团划分算法ITG，通过在模拟网络数据集和真实网络数据集上进行实验，验证了所提算法的精确性和新颖性，并优于FastGN, OSLOM和Infomap等经典算法。

关键词：有向社团划分, 信息传递增益, 目标函数优化, 算法可扩展性

基金资助：国家973 计划项目(2013CB 329600)，教育部哲学社会科学重大攻关项目(15JZD027)，十二五国家科技支撑计划国家文化科技创新工程2013 年备选项目(2013BAH43F01)