1引言
随着社会媒体的发展，在线社会网络成为重要的信息传播平台．社交网络和微博网站如Facebook、Twitter和Googleplus每天要支持几十亿用户的信息分享活动．通过这些系统，人们随时随地的交流观念、分享相册和视频等信息．不同于传统社会网络，在线社会网络展现了一些特殊特征:用户是信息的创造者、接受者和传播者．信息成为除用户以外的主角，它展现了用户之间的社交内容．凭借信息，用户表达了其情绪和观念，而用户对信息的一系列操作表现出了用户的社交行为．在社会网络中，用户之间的关系可能是朋友关系，可能是关注关系，也可能是通过同一信息进行交互的关系，这种包含多种语义的关系称为异构交互．因此，我们将用户实体和非用户实体共同存在，且实体之间存在异构交互的社会网络称为异构社会网络．异构社会网络中，许多因素促使了用户之间的网络拓扑结构的演变，其中关键因素是信息传播［1］．初期，社会网络的构型只是多个非连通的稀疏子图，用户之间是否存在交互，主要依赖于其在现实生活中的社交圈子．而随着信息的传播，用户能够随时随地的获得最新消息，透过这些消息，能够对其他用户相关的如偏好、权威等信息有更多的理解．进而，主动与自己感兴趣或崇拜的用户直接产生关联并互动，使得网络用户之间的网络拓扑构型变为或密集或稀疏的连通图，而这样的网络拓扑也为信息传播提供了更便利的条件．受兴趣或权威等的影响而聚在一起的用户团体，具有高度的互动性，也就更明显的体现出了社团结构．因此，异构社会网络中，社团的形成和信息传播相互影响:信息传播促进社团的形成，而社团的形成又进一步影响信息传播［1］．信息传播不仅体现网络结构特性，同时也体现用户之间的互动行为，其本质上展现了用户影响力的传播．信息不仅包含单纯的内容，更重要的隐含了原创者或传播者的兴趣或威信，称为活动影响力．除此之外，用户在网络拓扑结构的位置也是影响信息传播的一个重要因素，如其邻居的多少，邻居之间关系的紧密程度，决定了信息出现在其他用户视野内的时间、频率及经过的传播路径，从而决定了信息传播的范围和速度，称为结构影响力．因此，信息传播实质上是用户的结构影响力和活动影响力不断作用的过程．用户之间建立或取消关系，或进行评论等交互行为，也就不再是随机的，而是反映了受影响的结果．所以，社会网络中的网络拓扑结构的演变和用户之间的社交行为都是用户影响力传播导致的结果．那么，基于用户影响力传播来研究社会网络中的社团结构也就有据可依，而且可以实现对社团演变的预测．现存的社团发现方法，主要通过用户之间的网络拓扑结构来定义边权重，也有少部分的基于结构和属性的方法来寻找社团．但是，极少的方法将影响力传播考虑到社团发现中．文献［20］提出将独立级联传播模型用于寻找社团，但只是用传播模型确定出节点能影响的邻居节点，并没有真正意义的利用用户影响力传播过程来寻找社团．所以，本文提出的基于节点影响力传播的社团发现方法，不仅仅考虑网络结构，更多从社会网络的社会性，互动性，传播特性等方面来综合考虑社团的形成．在异构社会网络中，用户的社交行为和社交内容很丰富，用户之间的相互影响更加明显．所以，在异构社会网络中，使用基于节点影响力传播来发现社团也就更有意义．但是由于异构社会网络中包含多种实体、静态属性和动态活动，社团发现问题将会面临新的挑战．如异构网络中理想的社团需兼顾结构上的社团特性(社团内和社团间的连接边的紧密稀疏程度)和活动上的社团特性(社团内和社团间的社交内容和社交行为类型的相似程度);如何有效的利用社交行为和社交内容分析大规模的异构社会网络;如何定义用户的结构影响力和活动影响力，并且将二者统一起来描述用户之间的相互影响概率;如何发现重叠社团等．认识到这些新的挑战，本文提出了一种新的社团发现的思路———基于节点影响力传播的社团发现算法．由于节点之间的影响力是相互的，且不平衡的，因此需要考虑节点之间的相互影响概率．同时网络拓扑结构节点的位置对信息传播也具有重要作用，需要定义结构中心度来表示结构影响力(§3.1);另外，节点活动影响力也是节点之间信息传播和产生相互影响的关键因素．我们利用异构社会网络中的社交内容和社交行为信息，提出了定义活动权威性和社交行为相似性的方法(§3.2)．最后将结构中心度和活动影响力统一起来，定义节点之间的相互影响概率(§3.3)．在§4中，我们对原始标签传播算法进行改进，综合考虑影响概率、潜在重叠节点及相应的标签选择策略，提出基于节点影响力传播的可重叠社团的发现算法．在§5实验中，首先验证了提出的结构中心度的合理性，与经典的k-shell［21］进行对比，效果近似，但结构中心度能给出更加精确的影响力值．然后，将本文提出的社团发现算法同时在同构和异构网络上进行实验，实验结果表明我们的算法在异构社会网络中发现的社团，不仅保证社团内网络结构的紧密型，同时兼顾了社团的社会特性:同社团的用户互动性较高．
2相关工作
社团发现是社会网络分析的一个研究热点，随着在线社会网络的发展，特别是海量数据和社交互动的社会性都对社团发现的研究提出了极大的挑战．近些年来提出了许多社团发现的算法，有基于拓扑结构的，有基于结构和属性的．基于拓扑结构的算法研究比较成熟，其大致可分三类．第一类是基于启发式的，典型的有层次聚类．不同的层次聚类方法，主要区别是边权重的定义方法，其中包括边中心介数［2］，随机游走介数［2，6］，信息中心度［3］以及边聚集系数［4］，相似度动力学［5］等．第二类是基于目标函数优化的方法．自从Newman等人［2］提出基于模块化的零参数模型，就涌现了一类基于最大化模块化的社团发现算法，其中包括贪心算法［7］、模拟退火［8］、极值优化［9］和谱优化［10］等．第三类算法则充分利用了拉普拉斯矩阵［11］或正规矩阵［12］的谱特性．随着社会网络的发展，节点和边上也不断的出现属性信息，如节点表示的用户还具有表示自身特征的如兴趣、职业等属性．结合结构和属性的社团发现方法也就提供了新的思路．其中Yangzhou等人［13］提出的基于结构/属性相似度的k-centroid，ZhiqiangXu等人［14］提出的基于模型的属性图聚类．但是这些方法中，由于属性的类型丰富，结合拓扑结构描述节点之间的关系时，每一类属性的权重参数设置就成为这类方法中的一个主要问题．社团还有一个重要的特性:重叠社团．这个特性也是现实生活的真实写照，如一个人通常和多个社会团体有关联，如家族成员、朋友、同事或兴趣小组．比如，微博上的用户可以同时在多个主题的微博圈内活跃．基于重叠社团的特性，Palla等人［15］的基于子团渗透的CPM．Lancichinetti等人［22］提出的基于局部聚类统计特性的最优化方法OSLOM．基于CPM，WanyunCui等人［16］提出的重叠社团搜索方法OCS．Ahn等人［17］提出的链聚类，以及Henserson等人［18］提出的HCDF．但这些方法都是基于结构的，忽视了由于属性产生的重叠社团这个问题．Ｒaghavan等人［19］提出的标签传播算法，结合传播特性，将代表社团ID的标签沿着边传播，每个节点用最多邻居标签数的标签标记，迭代更新标签直到条件满足．该算法在保证一定社团质量的条件下，以接近线性的时间复杂度，实现社团发现．这种高效性使得该算法能够运用到大规模的社会网络中．Lee等人［23］提出的模拟人类交流行为的听说标签传播是基于标签传播的可重叠社团发现，但是由于为每个节点都分配多标签，在大规模图中内存消耗太大．Grego-ry等人［24］提出的基于原始标签传播的可重叠社团发现算法COPＲA，该算法控制了任意一个节点最多可属于多个社团的数目v，同时每个节点包含多个从属系数，而从属系数小于某个阈值则不考虑．
3节点影响力及影响概率
基于节点影响力传播过程来寻找社团，其核心在于定义节点影响力和节点之间的相互影响概率．细观传播过程，用户在网络中所处的位置和用户的活动权威对传播至关重要．以图1所示，a中节点1是一个活动权威度很高的节点，但是其邻居之间关系稀疏，则节点1的活动权威度是其能影响邻居与否的关键因素;而b中节点2活动权威度不高，但其处于其邻居中的核心位置，节点2能够直接对邻居产生影响，也可以通过受影响的邻居进而影响没有被节点2直接影响的邻居．所以，节点影响力受结构和活动上的影响力所影响．本文提出结合节点之间结构中心度和活动权威性的差距，以及用户之间的社交行为相似性来综合定义相互影响概率．在进行细节介绍之前，我们需要陈述几个基本概念．
3．1结构中心度
结构中心度是根据节点在社会网络图中的位置，表现出的对信息传播的能力．MaksimKitsak等人［21］提出，处于网络核心和网络边缘的节点，即便两节点度数相同，网络核心节点的传播能力明显高于边缘节点．其原因在于，网络核心的节点，其邻居在结构上相对紧密;相反，网络边缘的节点，其邻居在结构上相对松散．这就说明，在结构上，节点表现出的对信息的传播力，不仅与节点的度数相关，而且与节点的邻居的结构紧密程度相关．基于此，我们先考虑自我网络中，中心节点的局部结构中心度．
3．2活动权威性和社交行为相似性
异构社会网络是指存在多类型实体，实体之间存在异构交互的网络．其中，非用户实体展现社交内容，异构交互展现了社交行为．在分析异构社会网络时，社交行为和社交内容提供了更丰富的信息，利用这些信息能够更有效的量度用户的活动权威度和用户间的社交行为相似性．活动权威性描述用户在社交活动中所展现的影响力．社交行为相似性描述用户在社交活动中表现出的社交行为的近似程度，即在越多相同的非用户实体上参与活动，则两用户社交行为越相似．如用户u1，u2，u3在数据挖掘领域的三个会议(sigmod，icdm，www)中发文章数目的情况分别为u1［2，2，3］，u2［2，3，2］，u3［3，1，0］，则认为u1和u2的社交行为相似性高，u1和u3或u2和u3的社交行为相似性低．基于以上描述，要度量用户的活动权威性和社交行为相似性，就需要对非用户实体根据某些标准进行分类，即定义为高层抽象．定义3高层抽象．非用户实体按照其所属的类别，映射到更高层次的新实体，其可能一层映射，也可能是多层映射．如DBLP的文章实体经过多层映射，其先映射到会议实体，再将会议实体映射到领域实体．
3．3影响概率
节点之间的相互影响主要由节点之间的影响力差距造成的．社会网络的信息传播过程中，用户主动的接收并传播信息．而促使用户主动接收信息的原因主要是兴趣或权威驱动的，当发现某个用户传出的信息总是很切合自己的兴趣或者很有道理时，用户就会直接去关注并与之互动．
4可重叠社团发现
本文中，节点影响力传播的过程与标签算法的思想很相近，而且标签算法接近线性的时间复杂度，也是在大规模数据集上寻找社团的一大优势．所以，我们基于标签传播算法，综合考虑影响概率、潜在重叠节点及相应的标签选择策略对原始算法进行改进，以达到发现可重叠社团的目的．第一，基于节点影响力传播的新标签传播算法，初始化节点标签时，保证每个节点都能独立的选择标签，这样做使得传播过程中的标签不只是一个表示社团的ID，同时也能表现出对社团形成起关键作用的节点．其主要有三种标准:1)如果所有邻居对节点的影响概率都小于1.0，则该节点比任意邻居的影响力都大，那么节点保持自己的ID作为标签;2)对于潜在重叠节点，保留对其影响概率大于1.0的前ε%节点的标签作为自己的标签;3)对于非潜在重叠节点，仅选择对其影响概率最大的节点的标签;第二，在异步标签更新时，标签选择策略:对于非潜在重叠节点，选择邻居中数目最多的标签，如果出现多个标签数目相同，则计算各标签的影响概率总和，选择影响概率总和最大的标签;对潜在重叠节点，选择标签比较复杂．由于其位置的特殊性，可能受到多个高影响力邻居的影响，也可能受多个低影响力节点群的影响，而自身也有自己的影响力，所以其保留的标签是:前ε%高影响力节点的标签，如果低影响力节点群的标签不属于前ε%，则再保留低影响力节点群中最高标签数目的标签;如果有一定比例的邻居标签是潜在重叠节点的ID，则还需保留自身ID作为标签．ε的确定可以自定义，当ε越小，则保留的高影响力节点标签数越少．如图2所示，圆圈内数字代表节点ID，边上的数字表示邻居的标签．按照潜在重叠节点的标签选择，中心节点4应当保留标签1，2，3，4．
5实验
5．1实验数据集
我们主要使用异构社会网络DBLP和Digg上的数据集．DBLP中，节点表示作者和文章，然后再根据CCF中对计算机领域会议的领域发现和分区情况，对文章实体进行高层抽象，先映射到会议，再映射到领域，最终获得作者在各领域的活动权威性，根据作者在各领域不同会议中的发文章情况，计算出用户之间的社交行为相似性．特别的，为了进一步分析，我们还从DBLP中抽取了数据库/数据挖掘/信息检索领域的数据集DBDMIＲ．
5．2比较方法和评估
在可重叠社团发现算法［15，17，18，22，23，24］中，大多基于无权无向图，我们选择了CPM，OSLOM进行对比实验．CPM中社团被定义为最大子图，这样的最大子图能够通过旋转k子团的方式获得结构上紧密的节点，但是该方法时间复杂度较高．OSLOM是所有众多可重叠社团算法中效果较好的方法，时间复杂O(n2)．
5．3结构中心度合理性
通过在数据集Example，计算出k-shell和局部结构中心度，实验结果如图3所示．图3中虚线线条(位于下方)描述了各个节点在网络中的k-shell值，其中k-shell值为2，11，12，13，14，17，18．k-shell值越大，则说明其处于网络核心，根据［23］，这样的节点结构上的传播能力越强．使用公式(1)计算出的节点局部结构中心度如实线线条(处于上方)所示．
5．4同构社会网络实验
在选择的可直观判别实验结果的数据集Example，验证新的结构中心度和算法有效性．此时，影响概率按公式(4)计算，但是由于没有活动信息，所以w1=0，社团发现算法与算法1基本一致．在实验过程中发现，使用局部结构中心度和使用近邻结构中心度得到的结果基本没有差异，这也就说明:节点在自我网络中表现出的局部结构中心度基本能代表其更广范围内的结构中心度．
6总结
本文提出一种基于节点影响力传播的可重叠社团发现算法．首先，我们提出一种新的定义节点结构影响力的方法．其次，基于节点影响力差决定了节点之间相互影响概率的大小，提出了影响概率的定义方法．最后，提出的基于节点影响力传播的社团发现方法是对标签传播算法的改进，综合考虑了影响概率、潜在重叠节点及相应的标签选择策略，最终发现可重叠社团．实验结果证明，该算法能够有效并高效地发现异构社会网络中重叠社团．得到的社团不仅具有结构上社团特征，同时也兼顾活动上的社团特征．这种兼顾特性对社会网络具有特别重要的意义．
作者：赵玉蓉 王轶彤 吴铭泽 单位：复旦大学计算机科学技术学院
