论文部分内容阅读
研究表明,网络已成为现实世界中许多系统的存在形式,而大多数现实网络中都普遍具有一个共同特征,即社区结构。针对在线社会网络的众多研究方向中,有一个非常有商业价值的研究领域即重叠社区发现。重叠社区不同于之前图论中提出的网络社区的概念,主要区分点是在重叠社区中,节点可以归属于不同社区。对于在线社会网络,一个节点是一个真实的人物,这些节点理所应当的具备了人所特有的多面性,即按照不同的侧面可以属于不同的社区。因而重叠社区的概念更符合在线社会网络中社区的实际特征。本文提出了两种针对在线社会网络的重叠社区发现算法,所研究的对象是如twitter、新浪微博、豆瓣网等具有关注关系的在线社会网络。两种算法分别基于社会属性网络的两种属性:一种是基于动态属性的动态属性群算法,一种是根据静态属性进行社区发现的基于兴趣的标签传播算法。动态属性群算法的大体思路是先根据关注关系将整张网络图划分为两部分,如受关注度前10%的节点为动态属性节点,其余为普通用户节点。其后根据普通用户节点的关注关系对动态属性群进行聚类。最后根据聚类结果确定普通用户节点的重叠社区划分。因为关注关系是可以由网络中的节点动态修改的,关注对象是动态的,所以这个算法是基于动态属性的。基于兴趣的标签传播算法建立在标签传播算法的基础上,主体上使用社区重叠传播算法(COPRA)的思路,通过归属系数判断标签是否被保留,从而能够发现重叠社区。与之不同的是在标签传播过程中不再使用“倒数系数”来随机判断节点是否保留标签,而是采用衰减因子与节点特征算法(HANP)中对标签传播能力的刻画,保留每个节点在传播过程中收到的有传播能力的所有标签。标签传播的对象是在线社会网络中独有的“个人标签”的概念,经过类似动态属性聚类过程减少了传播的标签总数,大大加强了标签传播算法的语义性。本文提出的两种算法不同于传统的图论算法从节点或边的角度出发,更多的是从社会学的三元闭包角度出发,因而更加符合在线社会网络的形态特征,对于在线社会网络中的重叠社区发现更加有效。本文设计了一个通过删除已有边,使用社区发现算法重建边的方式来判断重叠社区发现算法的准确性。实验表明与传统的复杂网络以或图论思想中创造的重叠社区发现算法相比,虽然在模块度这个指标上略有差距,但在发现社区的精准度上有所增强。