本站原创摘 要： 近年来,社会网络簇结构挖掘取得了长足的进展,广泛应用在社会网、生物网和万维网等领域中.如何挖掘社会网络中各种潜在结构和信息成为研究热点.标签传播算法是一种能够利用少量已标记节点的标签信息去预测大量的未标记节点的标签的半监督学习算法.介绍了标签传播算法理论,给出了标签算法的特点,总结了标签传播算法在社会网络中的应用及发展趋势.
关 键 词 ： 标签传播； 社区发现； 社会网络
中图分类号： TP301 文献标识码： A 文章编号：2095-2163（2013）03-0037-04
Applied Research of Label Propagation Algorithm in Social Network
LUO Qiubin, ZHU Hong, LI Yunhui, CONG Eryong
（College of engineering, Harbin University, Harbin 150086, China）
Abstract： In the recently years, detecting munities of social works has made considerable progress, has been widely applied in the social works, World Wide Web, biological works and many other fields. How to tap the potential structure and information in social works has been known as hotspot.The label propagation algorithm （LPA） is a graph-based semi-supervised learning algorithm, which can predict the information of unlabeled nodes by a few of labeled nodes. This paper introduces the theoretical study of label propagation algorithm, provides its characteristics, and summarizes its applications and trends of developments in social work.
Key words： Label Propagation； Community Discovery； Social Network
0 引 言
在Web2.0技术高度普及的信息化时代,人们利用互联网去查找、发布和共享信息,通过这种交互信息方式实现个人交际圈的延伸和扩展.从数据挖掘观点来看,社会网络是由图表示的个体关系的数据集.图中的节点表示网络中的对象或者个体,图中的边线表示网络中对象之间的联系或者相互作用的连接关系；节点和边都可以带有属性,可以具有类标号,链接一般是单向的但不必是二元的,这种表示图一般很大.显然,图论中的图为社会网络的研究提供了一种直观表现形式[1].半监督学习（Semi-Supervised Learning, SSL）是一种将监督学习和无监督学习相结合的方法,其主要思想是：基于数据分布上的模型检测设,利用少量的已标注数据进行指导并预测未标注数据的标记,再整合归并至标记的数据集中[2].标签传播算法[3]（label propagation algorithm, LPA）是由Zhu于2002 年提出,就是一种基于图的半监督学习方法,其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息.
本文简要介绍了该算法的基本理论和特点,分析了其在社会网络中的主要应用,讨论其优缺点,并给出了可能的发展方向.
1.标签传播算法
1.1 基本理论
标签传播算法利用样本间的关系,建立关系完全图模型,在完全图中,节点包括已标注和未标注数据,其边表示两个节点的相似度,节点的标签按相似度传递给其他节点,标签数据就像是一个源头,可以对无标签数据进行标注,节点的相似度越大,标签越容易传播.由于该算法简单易实现,执行时间短,复杂度低且分类效果好,引起了国内外学者的广泛关注和积极投入,并将其广泛地应用到多媒体信息分类、虚拟社区挖掘等各类热点领域中.
根据LPA 算法基本理论,每个节点的标签按相似度传播给相邻节点,在节点传播的每一步,每个节点根据相邻节点的标签来更新自己的标签,与该节点相似度越大,其相邻节点对其标注的影响权值越大,相似节点的标签越趋于一致,其标签就越容易传播.在标签传播过程中,保持已标注数据的标签不变,使其如一个源头般将标签传向未标注数据.最终,当迭代过程结束时,相似节点的概率分布也趋于相似,可以划分到同一个类别中,从而完成标签传播过程[3].
1.2 算法描述
具体算法如下.
令（x1,y1）等（x1,y1）是已标注数据,YL等于{y1等yl}∈{1等C}是类别标签,类别数C已知,且均存在于标签数据中.令（xl+1,yl+1）等（xl+u,yl+u）为未标注数据,YU等于{yl+1等yl+u}不可观测,l≤u,令数据集X等于{x1等xl+u}∈RD.问题由此转化为：从数据集X 中,利用YL的学习,为未标注数据集YU的每个数据找到对应的标签.实现过程为：
首先,将所有数据作为节点（包括已标注和未标注数据）,创建一个完全连接图,其边的权重计算公式如下：
wij等于exp-d2ijσ2等于exp-∑Dd等于1（xdi-xdj）2σ2 （1）
其中,dij表示任意两个节点的欧氏距离,权重wij受控于参数σ.
为衡量一个节点的标注通过图中某边传播到其他节点的概率,在此定义一个（l+u）*（l+u）概率传递矩阵T ,矩阵元素Tij的计算公式如下：
Tij等于P（j→i）等于wij∑l+uk等于1wkj
（2）
其中,Tij是节点j 到i的传播概率.
同时,定义一个（l+u）×C的标注矩阵Y,令Yic等于δ（yi,c）.其中,第i行表示节点yi的标注概率,第c列表示类别,若Yic等于1,则表示节点yi属于c类别,否则为0.
通过概率传递,使其概率分布集中于给定类别,再通过边的权重值来传递节点标签.矩阵Y 的初始值并不重要,但是要确保其中每行都实现了标准化.具体描述如表1所示.
表1 LPA算法描述
Tab.1 The Label Propagation Algorithm description
LPA算法描述
输入： u 个未标注数据, l 个标注数据及其类别C .
输出： u 个未标注数据的标注.
第一步,初始化,利用公式（1）计算边权重矩阵wij,得到数据间的相似度.
第二步,根据上式得到的wij,利用公式（2）计算节点j 到i 的传播概率.
第三步,定义一个（l+u）×C维的标注矩阵Y.
第四步,每个节点按传播概率将其周围节点传播的标注值按权重相加,并更新自己的概率分布：
Fij等于∑l+u k等于1Tij, 1≤i≤l+u； 1≤j≤C
（3）
第五步,限定已标注数据,将已标注数据的概率分布重新赋值为初始值.重复步骤四,直至收敛.
Fij等于Yij,1≤i≤l；1≤j≤C
（4）
1.3 标签传播算法的特点第3期 罗秋滨,等：标签传播算法在社会网络中的应用研究 智能计算机与应用 第3卷
LPA是一种半监督学习算法,只需利用少量的训练标签作为指导,利用未标注数据的内在结构、分布规律和邻近数据的标记,即可预测和传播未标记数据的标签；无论数据分布的具体形状,都能通过标签传播,将其归并到同一个类.因此,可以处理包括音频、视频、图像及文本在内的各类标注、检索及分类,而且具有算法简单,执行速度快,可扩展性强,有效性好等一系列优点.社会网络组织形式丰富多样,需要处理的数据包括短文本、音频、视频等综合类别,这使得LPA在社会网络领域具有良好的针对性和适应性.
2.标签传播算法在社会网络中的应用
2.1 社会网络分析的基本概念
社会网络分析（ Social Network Analysis 简称为SNA） 是适应社会结构和社会关系的研究需要顺应发展起来的一种分析方法.社会网络指的是由多个结点（ 一组社会行动者） 以及各结点之间的连线（行动者之间的关系） 组成的集合.通常可用于描述和测量行动者之间的关系或通过这些关系流通的各种有形及无形的东西,比如信息、资源等.
在真实世界中,复杂网络在整体上呈现着一些基本统计特性,譬如：“小世界效应”是指复杂网络具有短路径长度和高聚类系数的特点[4]；“无标度特性”,是指复杂网络中的结点之度服从幂率分布特征[5].“社区结构特性”,是指复杂网络中普遍存在着“同一社区内部的结点相互连接紧密、而不同社区间的结点相互连接稀疏”的特点[6].
2.2 应用于社区发现
社区挖掘研究对于分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐性规律以及预测复杂网络的行为具有着重要的理论意义,呈现了广阔的应用前景.自从2002年Girven和Newman[6] 提出社区挖掘的概念至今,新的理论方法层出不穷,新的应用领域与日俱增.社区结构是复杂网络最重要的拓扑特性之一.当今社会网络中,发现社区结构有助于理解用户分布和用户行为.
标签传播算法在社区发现中有较多应用.2007 年,Raghan 等[7]首次提出将LPA 应用于社区发现,该算法简称为R 算法.其主要思想是利用网络结构作为指导来探测社区结构,每个节点可初始化为一个独特的标签,并在每一步迭代中,其节点标签选定为该节点为其大多数邻近节点的标签,并在这个重复进行的过程中,密集连接的节点组由一个独特标签变换成一个具有共识的社区节点,那些具有相同标签的节点便组合构成了同一个社区.该算法的流程包括：初始化、标签更新、添加具有相同标签的顶点归属于同一个社区.而且算法通过在空手道俱乐部网和美国大学橄榄球网的相应实验,结果表明其社区检测效果良好.此后,很多学者都展开了相关方面的深入研究,不断改进R 算法,使之更好地应用于社区发现.
Barber [8]等为了避免LPA 中所有顶点都分配到同一社区,改进R 算法,提出一种模块化标签传播算法（Modularity-specialized label propagation algorithm, LPAm）,即基于约束的LPA 监测网络社区.给定一个目标函数,使得LPA 受到约束,引入一个变量使其社区的模块度值实现最大化,将社区发现问题转化为目标函数最优化的求解问题.在具有相同标签彼此连接的顶点个数基础上,定义一个目标函数H,利用LPA 算法发现H 函数的局部最优值.
Liu等[9]针对上述LPAm 易在模块空间中陷入局部极大值,从而导致社区检测不准确的问题,提出将LPAm与多步贪婪凝聚算法（Multi-step Greedy Agglomerative Algorithm,MSG）相融合,设计了一种模块化、专业化的标签传播算法（ Modularity-specialized label propagation algorithm, LPAm+）.该算法利用MSG 同时合并多个相似社区,能够避免陷入局部最大值,更加精准地进行网络社区检测. 2.3 应用于语义网
SemTagP[10]算法是对LPA算法的扩展.与LPA算法中传播随机分配的标签不同,SemTagP算法中为用户分配的标签是用户自身使用的标签,且在传播过程中进一步考虑了标签的泛化关系.通过这种传播方式,能够将拥有具体标签的成员划归到同一上位词标签构成的社区中.语义标签传播过程如图1所示.
图1 语义标签传播示意图
Fig.1 Semantics Label Propagation
由图1可见,其中的sport为football、golf、swim、rugby的上位词,program为Ja、Python、Lisp的上位词,且右图中同一底色的节点均在同一社区内.
算法将社会网络当作有向图处理,但却未做加权分析.同时,算法仅考虑了标签间的语义关系,而未充分开发用户交互关系的语义信息,例如通过用户交互关系的类型或亲密程度来评价用户间的影响力.
ISLPA[11]算法仍使用语义标签作为传播对象,与SemTagP算法不同,ISLPA算法在传播过程中并不检测标签间的语义关系,而是根据标签的语义关系和网络社区划分的尺度要求,在标签传播前预先对标签进行统一的语义处理.在语义标签传播更新过程中,算法将在线社会网络抽象为有向加权图,图中节点表示用户,边表示用户交互关系,边的权值表示某种交互关系对应的影响力.在不同交互关系下的邻居节点具有不同的影响力,因此要根据用户交互关系为边赋予权值.根据边的连接关系和边的权值大小为每个节点生成一个候选标签列表,标签列表含有语义标签及其对应的分数.各个节点选择对应列表中分数最大的标签,更新原有标签.算法迭代运行,直到节点的标签不再变化时,算法终止.
LPA-SNA[12]算法在原始 LPA 算法的基础上,当待更新节点的大部分邻居节点所属的簇结构不止一个,即该节点的邻接子系统不唯一时,基于节点属性相似度的标签传播算法（LPA-SNA）将计算每个邻接子系统中节点属性的平均值,进而计算待更新节点与各邻接子系统的属性相似度,同时选取可令相似度MaxSimi（si,SNir）最高的子系统的标签作为当前节点的标签.算法以网络结构为主要依据的同时,又考虑了节点属性信息,对大规模数据集网络进行聚类,一定程度上克服了原始LPA 算法的随机策略,提升了算法的聚类速度,也提高了网络划分质量.
2.4 应用于推荐系统
互联网技术的迅猛发展带来了信息爆炸.而个性化推荐系统通过建立用户与信息产品之间的二元关系,利用已有的选择过程或相似性关系挖掘每个用户潜在感兴趣的对象,进行个性化推荐,其本质就是实现信息过滤.个性化推荐系统不仅在社会经济中具有重要的应用价值,而且也是一个值得重点研究的科学问题.
标签推荐系统依据其推荐策略可分成基于内容的标签推荐系统、协同标签推荐系统、基于图的标签推荐系统.其中,基于图的标签推荐系统是将用户、资源、标签三者的关系构成三维的图结构,利用图结构进行标签推荐[13].有代表性的是FolkRank[14],其主要思想采用了重要性传递理论.重要的用户采用了重要的标签所标注的资源,意味着该资源也是重要的,同理,标注在重要资源上的标签,该标签也是重要的.基于此思想,标签系统中资源、用户、标签三者的关系将通过这种方式互相增强,形成了完全的三维关系图结构,采用基于图遍历的算法即可完成标签推荐,常见的推荐思想是采用随机走算法在关系确定的图结构中为用户确定推荐的标签.
2.5 其他应用
个性化社会标签是社会网络一系列算法的研究实现基础.标签传播算法还可以应用于网页的重要度排序,可扩展到垃圾信息的屏蔽、信任评价等；另一方面,标签传播算法也可以合并迁移学习,进行情感分类方面的研究.
3.结束语
社会网络的研究还刚起步,很多领域还有待进一步地开拓与研发.LPA是一种通用的半监督学习新方法,能够利用少量已标注节点预测未标记节点的标签信息,该算法在理论和实际应用中表现了众多的优越性能.本文介绍了LPA在社会网络研究中的基本应用,包括社区发现、语义网、推荐系统等.随着研究的深入,LPA算法在社会网络中的应用将得到进一步深化与发展.