基于标签传播算法的Web社区发现研究

阎海玲　周瑞　袁春艳

摘要：标签传播算法是社区发现的经典算法，优点是思路简单，快速高效；缺点是随机性强，每次迭代结果不一致，准确率不高。Web系统是一个由超文本链接构成的巨大的信息源，将改进的标签传播算法用于Web社区发现，有助于快速在大量的Web页面中发现有利用价值的信息。

关键词：标签传播；Web；社区发现

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）02-0254-03

Research on Web Community Detection Based on Label Propagation Algorithm

YAN Hai-ling，ZHOU Rui，YUAN Chun-yan

（XingZhi College of Xian University of Finance and Economics，Xi'an 710038，China ）

Abstract：Label propagation algorithm is a classical method for community detection， it's advantage is high efficiency and simplicity， it's disadvantage is strong randomness and low accuracy quality because the results of iteration every time are inconsistent. Web system is a huge information source that made up of hypertext links. It's useful in that it uses improved label propagation algorithm on Web community detection.

Key words：label propagation；Web；community detection

客观世界可以看成是复杂的网络系统，是由形态各异的子系统构成。每一个子系统表现出社区结构的特性。在客观世界中，不同的社区结构表示不同的内容，具有不同的含义。例如人际关系网中，相识的关系密切的朋友可以划分为同一个社区；在生物学系统网中，相同功能的组织单位可以划分为一个社区。对社区发现的研究，可以在不同领域获取可靠有价值的信息。近年来，社区研究的主要方法划分为四大类：图分割方法、W-H算法、层次聚类法以及标签传播算法[1]。

其中标签传播算法具有简单、高效的特点，但是准确性有待于提高。其主要原因在于在选取节点的邻接点时随机选取，这种随机性导致计算结果不一致，从而导致社区划分的准确性降低。针对标签传播算法的缺點，研究者们提出了多种改进的方法。在标签传播基本算法的基础之上提出了多种基于标签传播算法的新思路。

1 标签传播算法

标签传播算法（Label Propagation Algorithm，LPA）的基本思想就是相似的数据应该具有相同的标签，具有相同标签的数据划分为同一个社区。也即一个节点应该和它的大多数邻接点划分为同一个社区。将网络看做是一个无向图，首先给图中每一个节点随机分配一个唯一的标签（初始时可以认为每一个节点就是一个单独的社区），然后将一个节点的标签更新为所有邻接点的标签中数量最多的那个标签，最终标签相同的节点划分为同一社区结构。

标签传播算法是基于图的，将网络系统转化为图进行研究。将所有的数据构建成一个图，每一个数据点就是图中的一个节点，假设这个图是全连接的，包含已标注过的和未标注的两种数据。节点v和节点w的边表示他们的关联度。给每个节点随机分配一个标签以代表它所属的社区，遍历图中每一个节点，将每一个节点的标签更新为它的所有邻接点中标签数目最多的那个标签，如果数目最多的标签同时存在多个，则在其中随机选择一个进行更新，最终同一标签的节点划分为同一个社区结构。每一个节点的标签取决于它邻接点的标签：假设节点v的邻接点有v1至zk，将v的标签更新为v1至vk 中标签数目最多的那个标签。也即v的邻接点中哪个社区的标签最多，v就属于哪个社区。标签传播算法时间复杂度接近线性：对图中每个节点分配标签的时间复杂度为O（n），每次迭代时间为O（ m），划分出所有社区的复杂度为O（n +m）。

标签传播算法详细步骤：

①初始时，给每个节点随机分配一个唯一的标签（每个节点是一个单独的社区）；

②用每个节点的邻接点的标签中最多的标签来更新自身的标签。

③反复执行步骤②，直到每个节点的标签稳定不再发生变化为止。

图1为只有4个节点的单个社区标签传播的过程，首先为4个节点随机分配 A、B、C、D 四个不同的标签（初始时认为4个节点各自属于一个社区），而后随机选取节点B进行更新，节点B在3个邻居标签中随机更新为标签A。然后选择节点C，节点C的邻居节点中只有一个频率最高的标签A，其标签更新为A，最后节D点的三个邻接点标签均为A，则节点D的标签也更新为A。此时，所有节点均划分为同一社区，算法结束。

2 几种改进的基于标签传播的非重叠社区发现算法

针对传统的标签传播算法的准确性低下的特点，众多研究者在传统标签算法的基础上进行了改进。如：宋琛的基于随机游走相似度矩阵的改进标签传播算法，引入随机游走的算法计算节点间的相似度，得到衡量节点间相似度的矩阵，然后选择相似度最高的邻接点传播，从而达到提高准确性的目的；张素智、孙嘉彬、王威等提出的基于节点聚集系数的分布式标签传播算法，在标签更新过程中引入节点聚类系数，提出一种结合MapReduce分布式计算框架的社区发现算法——DisLPA算法，提高了准确率同时改善了计算瓶颈问题。李磊，倪林提出了基于模块度优化的标签传播社区发现算法——LPAMP。该算法降低了标签传播算法的随机性，增强了稳定性，并且提高了准确率。张超，武先强，董荣胜在现有的基于相干邻居亲近度的标签传播算法中，引入节点间依赖度，提高了社区发现的准确性，减少了标签传播过程花费的时间。徐成林，陈志刚，黄瑞等人在标签传播过程中综合考虑节点重要性以及邻居标签的数量提出LRDC，显著地提高了社区发现的准确性和稳定性。endprint

以上改进的标签传播算法，主要是针对在标签传播过程中，对于某一个节点，当其邻接点的标签最多的个数不唯一时，随机选一个。这种随机性导致每次迭代结果不一致，降低了社区发现的准确性。针对这种不确定性，在算法中引入某种衡量的参数，更新节点的标签时，若该节点的邻接点的最多标签数目有多个时，不再是随机选取一个标签进行传播，而是根据衡量的参数值来选取，从而提高了算法的准确性和稳定性，社区结构的质量也就随之提高。

3 Web社區发现相关的基本概念

Web作为一个巨大的信息源，其内容和形式多种多样，并没有一个完全统一的规格和模式。正是由于具有这样的特点，人们起初认为Web页面是无结构数据。但是随着互联网的迅速发展和Web资源的急速扩充，对Web网络研究的逐渐深入，人们意识到Web资源应该是介于结构化和无结构数据之间，属于半结构化数据。按照不同的标准划分，可以划分为不同的社区。在Web社区发现过程中需要注意以下几种特殊含义的页面：噪音页面、权威页面和中心页面。

噪音页面，如果一个Web页面的内容和Web社区的主题不相关，则把这个页面称之为噪音页面。噪音页面越少，社区质量越高。

权威页面：人们普遍公认在某一个主题上具有权威性的页面。当一个Web页面的设计者在该页面上创建指向另一个页面的超链接是，可以认为该设计者对另一页面的认可。如果一个Web页面被不同的Web页面设计者认可，则可以从某一角度说明该页面的重要性，从而发现权威页面。一个权威页面很少让它的超链接指向其相同领域竞争者的页面。

中心页面：指向权威页面的超链接集合的页面。一个好的中心页面指向很多好的权威页面。而一个好的权威页面被很多好的中心页面所指向。

中心页面与权威页面之间相辅相成互相增强的关系有助于权威页面的发现以及高质量Web社区的发现。

4 改进的标签传播算法在Web社区发现的应用

Web社区是互联网中客观存在的Web页面集合，通过Web社区的发现，可以有效地发现与某一主题密切相关的Web页面集合。设Web社区G有n个节点和m条边，将每一个Web页面设定为一个节点，页面间的超链接设定为边。链接到该页面的Web页面个数为入度，该页面链接的其他页面的个数为出度。由此得出一个有向加权图。

首先给出有向图的形式化定义：

其形式化定义为：

G=（V ，E）

V={x|x∈DataObject}，E={| v，w∈V∧p（v，w）}

P（v，w）表示从顶点v到顶点w有一条直接通路。若 ∈E（G） ，表示从顶点v到顶点w有一条弧。其中：v称为弧尾（tail）或始点（initial node），w称为弧头（head）或终点（terminal node） 。

图中n个节点构建一个n×n的矩阵，通过节点之间的边传播标签。边的权值越大，表示两个节点越接近，该节点的标签越容易传播。

将标签传播算法用于Web社区发现时，可以考虑从两个方面进行改进：分别在初始化过程中和在标签传播过程中。改进思路如下：

①标签初始化过程

在标签初始化过程中，可以给节点或边添加权重，将无向图转化为有向网描述节点的传播优先级，可以初步确定社区中心节点从而提高社区划分的质量。

②标签传播过程

在标签传播过程中，可以对标签选择的随机性进行改进。将Web页面内容的相似度或者超链接的点击率作为衡量的参数来计算边的权值，描述节点的传播优先度，然后选取权值最大的邻接点进行标签传播。例如在基于随机游走相似度矩阵的改进标签传播算法中，将Web页面内容的相似度或者超链接的点击率作为节点间的相似度，选取相似度最高的邻接点进行标签传播。

5 结束语

随着Internet的迅速发展，Web资源朝着多元化、复杂化方向飞速增长，但是对于用户来说只有很小一部分具有使用价值。因此，从复杂的Web系统资源中发现有利用价值的Web社区显得尤为重要。尝试将改进的标签传播算法用于Web社区发现，进一步完善Web社区发现的理论基础，提高Web社区发现的质量特性，促进复杂网络理论的发展完善，其理论基础可以推广到其他复杂网络的社区发现。

参考文献：

[1] 宋琛，张贤坤，费松，等.基于随机游走相似度矩阵的改进标签传播算法[J].计算机应用与软件，2016，33（08）：269-272.

[2] 张素智，孙嘉彬，王威.基于节点聚集系数的分布式标签传播算法[J].计算机应用与软件，2016，33（04）：125-128+142.

[3] 李磊，倪林.基于模块度优化的标签传播社区发现算法[J].计算机系统应用，2016， 25（09）：212-215.

[4] 张超，武先强，董荣胜.一种改进的基于相干邻居亲近度的标签传播算法[J].广西科学院学报，2017，33（01）：12-18.

[5] 徐成林，陈志刚，黄瑞，等.用于社区发现的LPA_LRDC标签传播算法[J].小型微型计算机系统，2017，38（08）：1746-1750.

[6] 张金增.一种改进的Web社区挖掘算法[D].郑州大学，2009.