Page 166 - 《软件学报》2020年第11期

3482 Journal of Software 软件学报 Vol.31, No.11, November 2020

algorithm is evaluated on both synthetic and real-world networks. The experimental results demonstrate that the proposed algorithm is
highly effective at finding local community of the given node, and achieves higher F-score than other related algorithms.
Key words: social media network; local community discovery; fuzzy similarity relation; community structure

近年来,以 Facebook、Twitter、新浪微博、微信为代表的在线社交媒体发展飞速.这些社交媒体有上亿的
注册用户,创造了海量的内容,用户与用户之间、用户与媒体内容之间、媒体内容与内容之间形成了关系复杂
[1]
的社会网络 .这些网络常呈现“同一组内节点连接紧密,不同组间节点连接稀疏”的社区结构特性 [2,3] .社区结构
刻画了网络中连边关系的局部聚集特性.社区发现类似于图划分、聚类的概念,对这个问题的认识,程学旗等人
[4]
澄清了它们三者之间的区别与联系,并给出了社区发现的问题界定 .社区划分与图划分的处理对象都是网络,
但图划分的目标是把网络中的节点划分成给定个数、大小相同的节点集合,要求划分所切断的边最小,而社区
发现是寻找网络中固有的自然划分,而不是按指定条件划分.社区发现和聚类在处理方式上相似,但二者处理的
对象不同,聚类所处理的是可以表示成高维向量的属性数据,而社区发现所处理的是表示成网络的关系数据.社
区发现的研究具有重要理论价值和实际应用意义,在过去的十几年里受到国内外广大学者的关注.例如,著名学
者 Fortunato、刘大有课题组、程学旗课题组等都对社区发现算法研究做了大量工作 [4−6] .然而,大多学者将网络
中个体与群体间相似性关系采用确定性度量,这样可能导致不合理的社区划分.真实世界网络结构中个体间的
相似关系可能是模糊的,个体对于社区的隶属关系也可能是不确定的.比如,社交网络中的好友关系就是一种模
糊关系,不同用户之间的友好度是不相同的.针对这一特点,产生了一些基于模糊或不确定关系模型的社区发现
方法.张泽华等人利用粗糙上下近似算法来研究社区局部扩展过程,提出了一种基于邻域粗糙化的启发式重叠
[8]
[7]
社区扩张方法 ;李刘强等人提出了一种基于模糊层次聚类的重叠社区检测算法 ;宋俐等人提出了一种基于
[9]
模糊聚类的社区发现算法 ;张云雷等人用社区的下近似集和上近似集来刻画社区的模糊区域,提出了基于粗
糙集理论的社区发现方法 [10] ;Wang 等人针对网络结构的复杂性和群体划分的不确定性,采用模糊方法来处理
网络节点间的相似性,实现网络社区结构的模糊划分 [11] .Sun 等人使用模糊关系的操作取代图的遍历搜索来识
别社区结构 [12] .Liu 等人提出一种基于模糊聚类的 K 均值算法来检测复杂网络中的社区结构 [13] .
以上的社区发现算法都是基于网络的全局结构.但随着大规模的 Web 网络和社会网络的出现,这些网络由
于规模太大而难以获取其全局结构,或进行全局计算复杂度过高,传统的全局社区发现方法无法有效处理这些
大网络.同时也产生了一些应用,例如基于用户偏好的推荐,需要挖掘某个用户所在的局部社区 [14] .局部社区发
现作为一种不需要知道网络的整体结构、仅通过分析给定节点或节点集的周围节点之间的关系就能够找出给
定节点所在社区的方法,近年来成为社会网络数据分析中的一个新的热点问题.相比全局社区发现,局部社区发
现方法相关的研究较少.基于此,本文针对真实世界网络结构中个体间相似关系的模糊或不确定性,提出一种基
于模糊相似关系的局部社区发现算法,将某一节点所在的局部社区转化为该节点关于模糊相似关系 q 水平上
的等价类,通过寻找给定节点所在的模糊等价类进行局部社区发现.首先,采用模糊关系来描述两个节点之间的
相似关系,用节点对的相似度作为该模糊关系的隶属函数;然后证明了该关系是一种模糊相似关系,将局部社区
定义为给定节点关于模糊相似关系的等价类,进而采用最大连通子图算法求得给定节点所在的社区.
综上,本文的主要贡献如下:(1) 提出了采用模糊相似关系来描述网络中两个节点之间的相似关系,并以节
点对的相似度作为该模糊关系的隶属函数;(2) 将局部社区定义为给定节点关于模糊相似关系的等价类,给出
了局部社区的一种新定义.基于该定义,提出了一种基于最大连通子图的局部社区发现算法;(3) 分别在仿真网
络数据集和真实网络数据集上与相关算法进行了对比分析,实验结果表明,本文算法能够有效地揭示出给定节
点所在的局部社区,与其他算法相比,具有更高的准确性.
本文第 1 节介绍局部社区发现的问题定义以及相关算法.第 2 节详细介绍本文算法,并通过实例说明本文
算法的计算过程.第 3 节介绍在仿真网络数据集和真实网络数据集上的实验结果.第 4 节对本文工作进行总结.