基于标签传播概率的重叠社区发现算法-计算机学报.PDF

第 卷 第 期 计 算 机 学 报 ３９ ４ 　 　　 　　 　　 　　 Ｖｏｌ．３９ Ｎｏ．４ 年 月 ２０１６ ４ Ａ ｒ．２０１６ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ ｐ 　 基于标签传播概率的重叠社区发现算法 刘世超 朱福喜 甘 琳 　 　 （武汉大学计算机学院 武汉 ４３００７２） 　 　 摘 要 发现高质量的社区有助于理解真实的复杂网络，尤其是动态地分析社区重叠结构，对社区管理和演化具 　 　 有重要意义 文中提出一种基于标签传播概率的 （ ）重叠社区发现算法， ． ＬＰＰＢＬａｂｅｌＰｒｏａａｔｉｏｎＰｒｏｂａｂｉｌｉｔＢａｓｅｄ ｐｇ ｙ 该算法首先为每个结点赋予一个独立的标签，然后根据结点的影响力大小将结点进行排序；在标签传播的过程中， 综合网络的结构传播特性和结点的属性特征计算标签传播的概率，同时利用结点的历史标签记录修正标签更新结 果；最后将传播后具有相同标签的结点划分为同一社区，社区间的重叠结点构成了社区重叠结构 作者在基准数据 ． 集和带时间维度的ＣＤＢＬＰ网络上进行实验，结果验证了该算法具有较高的准确性和稳定性，并且通过对重叠结 构的动态分析，揭示了社区重叠结点的行为特性和ＣＤＢＬＰ网络处于高“耦合度”的发展趋势． 关键词 重叠社区；标签传播概率；结点影响力；社区演化；社交网络；数据挖掘；社会媒体 　 中图法分类号 号 ／ ＴＰ３９１ 犇犗犐 １０．１１８９７ＳＰ．Ｊ．１０１６．２０１６．００７１７ 　　　 犃犔犪犫犲犾犘狉狅犪犪狋犻狅狀犘狉狅犫犪犫犻犾犻狋犅犪狊犲犱犃犾狅狉犻狋犺犿犳狅狉 狆犵 狔 犵 犗狏犲狉犾犪 犻狀 犆狅犿犿狌狀犻狋犇犲狋犲犮狋犻狅狀 狆狆 犵 狔 ＬＩＵＳｈｉＣｈａｏ ＺＨＵＦｕＸｉ ＧＡＮＬｉｎ 　 　 （ ， ， ） 犛犮犺狅狅犾狅 犆狅犿 狌狋犲狉 犠狌犺犪狀犝狀犻狏犲狉狊犻狋 犠狌犺犪狀 ４３００７２ 犳 狆 狔 　 犃犫狊狋狉犪犮狋 Ｆｉｎｄｉｎ ｈｉｈ ｕａｌｉｔ ｃｏｍｍｕｎｉｔ ｈｅｌｓｔｈｅｕｓｅｒｓｔｏｕｎｄｅｒｓｔａｎｄｔｈｅｒｅａｌｃｏｍ ｌｅｘ