论文部分内容阅读
社会网络分析起始于二十世纪三十年代,目前已经成为社会学、数据挖掘等领域中的一项重要研究课题。在实际中,社会网络是广泛存在的,如科研引文网络、社会关系网络、蛋白质交互网络等。而在社会网络中,节点往往都是成群、成组出现的,这种结构通常被称为社区。因此,对于社区结构的探测是有着实际意义的。传统的社区探测方法得到的结果只能使得节点属于唯一一个社区,但是在真实的社会网络中,节点往往会出现重叠的情况,因此,重叠社区探测更有着实际意义。在2005年,Plla等人在Nature上首先发现了社区重叠现象,并提出了一种用于重叠社区探测的社区探测方法。随后,在重叠社区探测方面,许多方法如雨后春笋般出现,使得重叠社区探测问题成为社区探测中的一个热点问题。连接聚类(Link Clustering, LC)是Ahn等人于2010年在Nature上提出的一种用于重叠社区的探测方法。传统的方法是以节点为研究对象,而LC方法是以连接作为研究对象。LC方法首先计算每条连接之间的Jaccard距离,这样会得到衡量连接之间相似程度的相似度矩阵。将相似度矩阵中的行向量看作是欧式空间中的点,LC方法采用层次聚类的方法对这些点进行聚类,在得到层次聚类的结果树状谱系图后,使用分割密度对其进行划分,得到最佳的划分层次,进而得到社区划分结果。该社区划分结果是对连接进行的社区划分。在结果中,连接是属于唯一的一个社区的,但是对于节点来说,连接一个节点的连接会有很多条,因此,在将连接的社区结果转化为节点的社区结果之后,会出现节点属于不同社区的情况,这样就自然的得到了重叠社区的探测结果。但是,在原始的连接聚类方法中,并未考虑非公共节点的连接之间的相似程度,因此,本文提出了一种拓展的连接相似度(Extended Link Similarity, ELS),并基于这种连接相似度提出了一种用于重叠社区探测的改进的连接聚类方法(Extended LinkClustering, ELC)。改进的方法中首先会根据拓展的连接相似度计算连接之间的相似度矩阵。之后会采用与LC类似的层次聚类方法来对相似度矩阵进行聚类,最后,对结果的树状谱系图使用EQ评价指标来进行评价。由于拓展的连接相似度考虑了没有公共节点之间的连接相似度,因此,改进的方法会为社区划分提供更多的信息。而且,使用EQ值来发现层次聚类的最优划分来进行社区划分比原始方法中使用分割密度进行划分更合理。在五个实际数据集:空手道联盟数据集、海豚数据集、美国政治图书数据集、美国大学橄榄球联盟数据集、Y2H蛋白质交互网络数据集表明,与原始的连接聚类方法和经典的CPM方法相比,本文提出的方法会得到更高的重叠社区模块度EQ值以及更接近实际的社区数目。同时,还进行了人工数据集的实验,并根据网络数据集中的节点平均度和社区内部连接比例情况给出了ELC、LC和CPM三种方法所适用的网络的特征。