模糊谱聚类重叠社区发现算法

Overlapping Community Discovery Algorithm Based on Fuzzy Spectral Clustering

闫晓鹏1孙永波2(江西师范大学计算机信息工程学院1，江西南昌　330022;莱芜钢铁冶金生态工程技术有限公司2，山东莱芜　271104)



模糊谱聚类重叠社区发现算法

第一作者闫晓鹏(1990－)，女，现为江西师范大学软件工程专业在读硕士研究生;主要从事本体论和语义Web、数据挖掘、社会网络分析方面的研究。

0　引言

早期的社区发现研究是针对非重叠社区，认为网络可以被分割成若干个互不相连的社区，每个节点只能属于唯一的社区。然而，在实际的社交网络中，存在一些节点同时隶属于不同的社区，且这些节点在社区间的信息传播和演变中起着重要的中介或过滤的作用，能够衔接各个社区。为此，研究者们陆续提出一系列算法来挖掘网络重叠社区。例如:派系过滤算法(clique percolation method，CPM)［1－2］;基于标签传播的算法:社区重叠传播算法(community overlap propagation algorithm，COPRA)［3］、平衡多标签算法(balanced multi－label propagation algorithm，BMLPA)［4］、扬声器监听器标签传播算法(speaker－listener label propagation algorithm，SLPA)［5］等。基于局部社区优化和扩展的算法包括:局部适应度最大化(local fitness maximization，LFM)［6］、贪婪团扩展(greedy clique expansion，GCE)［7］、平等识别网络中模块组织(democratic estimate of the modular organization of a network，DEMON)［8］、序列统计局部最优方法(order statistics local optimization method， OSLOM)［9］等。基于链接聚类的方法包括:基于链接图划分的LINK算法［10］、基于映射方程的连接社区(link community)发现方法［11］、基于链接最大似然(link maximum likelihood)的方法［12］等。

但是在重叠社区发现中产生冗余社区仍是目前研究面临的一个问题。针对该问题，提出一种基于模糊谱聚类的重叠社区发现算法(fuzzy spectral clusteringbased overlapping community discovery，FSC－OCD)。

1　谱图理论

谱图理论使用线性代数理论和矩阵理论来研究图的邻接矩阵，并进一步研究图中所包含的信息。

为简化计算，将拉普拉斯矩阵进行归一化，表示为: