基于情感网络的社群发现与增长∗

2019-03-26张思敏

计算机与数字工程 2019年3期

马力张思敏

（西安邮电大学计算机学院西安 710061）

1 引言

随着以社交和资讯分享为主的在线社交应用（如微博、微信、facebook等）及在线评论的兴起，不同人员之间已经构筑起了一个无缝的信息共享与交流平台。它们一方面增强了人们信息交流的多媒体性与时效性体验，另一方面还使人们对信息的需求从简单的获取与共享上升到情感表达层面。因此，进一步拓宽人们信息利用的深度，引起了众多学者的广泛关注。

情感是人类智能或认知的重要标志，是驱动人类行为发生的内在心理动因。它影响着人们的决策、学习和交流，并在人们的决策行为中起重要甚至决定性作用。认知心理学研究表明：人们的信息交流行为是受情感影响的。真实社会中人们的情感随其行为表示出来，并通过社会关系链传播。

当尝试着描述某一系统中元素以及元素之间相互连接的概念时，“网”这一形式成为了自然的选择，所以研究情感在个体之间如何传播这一问题时，在复杂网络理论基础上提出了情感网络的构建方法，基于在线网络数据读取进行网络生成、网络社群划分，提出基于网络社群的网络增长算法。

2 情感网络构建

采用图的概念来构建情感网络。由文献［3］和［5］定义情感网络图结构：用图结构表示，一个情感网络图G=（V，E，P），其中V表示情感网络中所有节点的集合（nodes），E表示为情感网络中所有节点之间连接关系的集合（edges），而P则用来表示情感网络中每个节点情感的属性（emotion）。

在构建社交网络的过程中经常采用读取已有网络数据和模拟网络生成的两种方式，但在线爬取的网络数据往往又很难做到数据的完整性，模拟生成的网络又难以说明现实网络复杂问题。所以参考构建社交网络的过程，根据文献［1］，我们对于构建情感网络设计了如图1的流程。

图1 情感网络流程图

3 基于在线读取的网络生成

由文献［10］建立一个模拟的微博用户关系表，记录了7位用户之间的关注与被关注的关系。例如，关系id=1则说明了a用户对于c用户进行了关注，把关系记做edge（c，a）。关系id=3则说明了e用户对于c用户同时也进行了关注的行为edge（c，e）。而关系id=9则说明了c用户对于e用户同时也进行了关注的行为edge（e，c）。

表1 模拟数据集

根据文献［6］用矩阵表示法首先描述表4.1数据集，网络当中包含了7各节点，因此可以构造一个7*7的矩阵G=（gi，j）来描述该网络关系。在这一网络当中如g1，3=1则表示了关系id=1，如g1，2=0则表明了a与b之间不存在连接的关系，在矩阵中所有元素不为0则为1。上表的数据就可以转化为以下矩阵G7。

4 网络社群的发现

社群划分类似于聚类，社群结构特点：社群内边密度要高于社群间边密度，社群内部连接相对紧密，各个社群之间连接相对稀疏。

社群发现有五种模型：点连接、随机游走、自旋玻璃、中间中心度、标签发现。

评价社群三个指标：模块化指标Q、网络聚类系数、网络密度。

4.1 基于交互特征的层次聚类算法

1）将用户的交互特征作为一个重要的社会属性，引入到社群结构发现工作中，构造了描述社交网络中用户相关度的模型；

2）提出了相应的社群发掘算法，它能够实现更加细粒度的社群发掘。

该方法的具体流程包括用户相关度计算、社区关联矩阵构建、社群聚类树生成和面向不同粒度的社群分割。通过用户相关度模型计算用户之间的相关度，将社交网络中的用户之间交互操作转化为权值，进而生成社群聚类树，根据需求分割为不同粒度的社群。

4.2 用户相关度模型

网络社群中的用户通过社交网站为媒介进行联系。根据文献［2］得知用户之间的相关程度，可以通过他们基于网站的强关联操作和弱关联操作体现。强关联操作指的是用户之间较为直接的交互关系，如转发、评论、分享等操作。弱关联操作指的是用户之间不太明显的交互关系，如关注同一个公共页面，经常到达相同的地理位置或共同使用同一个网站应用等。

为了表示用户之间的相关程度，本文采用用户之间的几个常见的强关联操作作为依据来衡量用户之间的相关程度，具体如式（1）所示：

式中，ηij表示用户i和用户j的相关度，αij表示用户i对用户j的评论次数，βij表示用户i对用户j的转发次数，λij表示用户i对用户j的分享次数；h1，h2，h3分别表示评论、转发、分享这3种操作的权值。为了确定h1，h2，h3，我们分别随机抽取N条评论、转发和分享记录，

分析发生在好友之间的评论、转发和分享的发生次数分别记为h1，h2，h3，则h1=n1/（n1+n2+n3），h2=n2/（n1+n2+n3），h3=n3/（n1+n2+n3）。

基于用户相关度，我们可以对社交网络中的任何两个用户之间的交互相似度进行度量，确定用户之间的强交互的相似程度。下面对于该问题进行形式化描述。对于一个含有n个用户的社群Q，设其中的用户分别为U1，U2，…，Ui，…，Un，对于其中任意用户Ui，通过式（1）的用户相关度公式，可以计算出他和其它N-1个用户的相关度。

定义向量：

为用户i社群相关度向量，则该向量表示用户i对于社群中所有用户的相关度。

计算出社群中所有用户的相关度向量Ai后。定义矩阵：

为社群Q的相关度矩阵。矩阵RMQ包含了社群Q中所有用户之间的相关度数据，反映了所有用户之间的相关性情况。

通过用户相关度模型，根据文献［6］，将网络社群内的用户之间的关系表示为向量空间的形式。如果矩阵中两个用户的相关度向量相似性越高，说明他们的交际圈重合度越高，则他们属于一个社群的概率也越大。因此，社群挖掘就转化为了向量聚类问题。将社群内的用户分为N个不同的社群，即将相关度模型中的用户矩阵聚类为N个向量集合。考虑到聚类的数量无法事先得知，本文提出了一种考虑噪音过滤的层次聚类方法，其可以根据需求，给定不同的聚类数量，得到不同粒度的聚类结果。

层次聚类方法是对给定的集中的数据，通过计算两两之间的距离，进行层次的分解或合并，直到某种条件满足为止。传统的层次聚类方法的结果是将一棵二叉树根据需求分割为若干数量的子树，这种方法的缺陷是对样本信息的完备性依赖太强，无法区分噪音数据。

为了解决这个问题，本文提出了一种改进的层次聚类算法，如图所示。首先，基于采集的用户之间的交互操作信息，对于一个包含n个用户在线社交网络Q，可以计算出其用户之间彼此的相关度矩阵RMQ。

对n个相关度向量层次聚类，首先计算彼此之间的马氏距离，从而得到一个n*n维的距离矩阵DMQ，显而易见，该矩阵相对于对角线对称且对角线元素为O，其他的元素dij就代表了向量和向量之间的马氏距离。基于层次聚类的思想，我们选取DMQ的下三角矩阵DMQ'，选取其中最小的元素dpq，这说明了向量和向量距离最接近，将这两个向量合并为一个新向量，在中去掉对应于的两行两列，再加上与其余向量之间的距离，其中与其他向量的距离取与该向量距离的较小值。这样，就把用户p和用户q合并成了一个名为用户r的子树，反复重复此过程，最终会形成整个社交网络所有用户的聚类树。

在得到聚类树后，我们可以将这棵聚类树裁剪为任意数量若干子树，每个子树就对应了一个社群，通过聚类数量的改变就实现了不同粒度的社群发掘。具体裁剪方法是：不断地选取根节点距离最大的两个左右子树，将其拆分为两个子树，或者将根节点距离最小的两个子树合并，直到数量和给定的聚类数量相等。在裁剪的过程中，我们不断删除子节点数量小于一定阈值的子树，视其为游离于社群之外的噪音数据。

在网络中社群的一般结构特点为：属于统一社群的内的节点之间边的密度要大于与其他社群之间的边密度，即同一社群内部的节点之间相互连接更为密切，而不同社群之间边的连接相对稀疏。模块化的指标Q更多地用来衡量节点之间社群化的程度，Q的核心思想就是期望同一社群内之间的节点关联尽可能地多，而对于不同社群之间的节点关联尽可能地少，公式如下：

其中，m表示整个关系网络中所有连接关系的总数目，eii为社群i里所有线的数目/m。eij表示了社群i内所有节点度数/2m。

依据文献［13］和［14］，本节在已经读取生成的社群基础之上，设计了基于社群的网络增长算法。通过网络社群的划分可以看出，在同一社群的网络节点具有较高的聚类特征，社群之间的节点连接与不同社群之间的节点连接关系紧密的多，所有网络的增长特征也应满足这一特征，同时也要符合网络的小世界特性。因此设计基于社群的网络增长算法，算法设计的基本流程如图2。由文献［12］第一步对已有网络结构进行随机游走的社区发现，第二步根据已发现的社群结构进行网络结构分割，第三步进行社群内的网络扩增，最后对于扩增完成的网络进行网络合并，完成网络的增长过程。

图2 网络扩增流程图

网络加入新节点h，首先随机分配进入网络的一个社群范围，根据该社群内节点的平均影响力大小即平均度数决定h节点的度数，随机按所给定的度数连接本社群内节点个数。下一节点i延续h节点增长策略继续进行增长。节点的增长在同一社群内使用BA网络模型的增长方式，通过文献［7］网络新增加一个节点，新增节点和已经存在节点vi相互连接的概率值∏i和节点vi的度ki以及节点vj的度kj满足如下关系：