结合评论信息与网络简化的电商平台社区发现算法

任豆豆 高娟

摘要：有效地发现网络中隐藏的社区结构是电商平台中进行高效推荐的一个前提。虽然已经提出了许多有效的社区检测算法，但很少有算法能对电商平台中用户评论信息进行充分利用，以达到解决社区发现算法准确性的目的。在本文中，根据用户结点的影响力的不同将结点分为领导结点和跟随结点，结点的影响力称为领导度和跟随度，根据结点的领导度和跟随度两个度量结合用户的评论信息的相似度提出将复杂网络简单化的方法，使简化后的网络与原始网络相比更容易观察到用户群结构，对简化后的网络进行划分以进行社区检测时更简单、准确。最后，在多个网络数据集上进行算法性能的测试，实验结果表明该算法能够更直观有效地揭示社区结构。

关键字：社区检测，评论信息，领导结点，跟随结点，网络简化

1引言

社区检测成为探索和理解网络如何工作的最重要任务之一，同样成为电商平台上高效推荐的基础，所以为了更好地进行用户推荐，首先应有一个好的社区检测算法。社区结构以网络的形式普遍存在，如社会网络[1]、生物网络[2]、引文网络[3]等，这使得社区检测对于更好地理解网络的组织结构、提取有用信息尤为重要。

然而，现有的社区检测算法在检测网络社区结构时很少考虑其可视化表达的理解，一个好的视觉理解可以帮助我们容易地识别出社区结构和内在特征。例如，一个社区通常包括两个重要的区域：核心和边界，这两个区域决定了社区的形状和组织，但是由于网络中存在大量的边缘结点，我们很难直接观测出其社区的内部结构。为了克服这一缺陷并且更好地进行社区划分，本文引入领导结点和跟随结点，并根据其影响力（领导度和跟随度）表征其与其他结点的关系。领导结点有较高的领导度，被视为社区的代表，跟随结点有较高的跟随度，表示网络中的边缘结点成员。一个社区的边界往往由几个领导度低、跟随度高的结点组成。因此本文提出了一种新的网络结构表示方法和社区检测算法，主要思想是根据结点的领导度和跟随度将复杂网络转换为简化的网络，该网络可以反映每个社区的核心成员以及每个结点的社区成员身份。 接着对化简后的网络进行最小分割完成社区检测。最后通过实验验证本文提出的方法具有更好的网络结构理解和更准确的社区划分效果。

2社区检测算法

给定一个原始的无向电商平台网络 ，其中V是包含n个结点的结点集，E是包含m条边的边集， 是邻接矩阵， 是边 的边权重，如果结点 和结点 之间存在边，则 =1，否则 为0，此外给定 为1。 是结点 邻居结点的集合， 是结点 的度。

对于任意两个结点，使用两个结点之间的公共邻居数量来反应他们的网络结构相似性，两个结点的公共结点越多两个结点就越相似。网络结构相似性计算公式为

根据用户结点和用户间存在的边可以观察到结点之间的连接关系，但不容易看到各个结点的社区结构。因此我们将网络社区结构中的结点分为领导结点和跟随结点，领导和跟随的程度定义为领导度和跟随度，用这两个度量来衡量一个结点的可表示性及其他結点与该结点的关系。领导结点作为社区的核心结点，领导度越高越可能是核心结点，一个跟随结点到其他结点的跟随程度较高，则这个结点和其核心结点越可能属于同一个社区。本文给定一个结点只能领导比它影响力小且跟它相似度高的邻居，如果它的一些邻居比它有更大的影响力，那么它就不能领导这些结点。此外，领导结点对跟随结点的影响力取决于结点间的相似性，如果相似度很高，那么领导结点对它们的领导力就很大。本文使用结点的度数相似性来反映结点的影响力，故而其邻居的数量越多，其领导程度就越高，影响力也就越大。故而结点的领导度定义为：

同样可以计算结点的跟随度：一个结点只跟随比它拥有更高领导的结点，它对某个结点的跟随程度取决于其共同邻居在其邻居中的比例，具体公式如下：

根据网络中结点的领导度和跟随度和用户结点的评论信息内容相似性将网络映射为有权有向网络，将原始网络结构映射为一个简单的网络。用户结点的内容相似性，通过对各个用户的商品评论信息进行内容提取并获取可以代表用户评论主题的关键信息，由于用户的评论信息多为短文本，故而本文认为每一个短文本仅涉及一个主题内容，将其进行向量化，并进行用户结点间主题相似度的计算，具体公式如下所示：

其中 表示用户结点i的主题向量表示，Jaccard（ ， ）表示两个用户结点间的内容相似性。利用用户结点间内容的相似性与跟随度结合，作为简化网络的权重，对于跟随结点只留取跟随结点与领导结点间权重最大的边的方法对复杂网络进行重新表示。将无向无权网络图重新表示为有向加权图 。权重计算根据结点的跟随度和跟随结点与领导结点间的内容相似性来确定，具体计算公式如下：

这里简单的认为用户结点间的跟随度影响力和内容相似性影响力同样重要，故而取影响因素权重都为0.5。

重新表示后网络表示如下：

重新表示之后的网络是一个树结构，这个网络有四个属性：第一、 中的边数不超过n−1，其中n为结点数;第二、设T为 的子树，对于T中任意的 ，由于 ，其根在T中的领导度L值最大;第三、对于任意两个结点 和 ，如果它们之间在 中有路径，则它们之间的路径存在于原网络G中;第四、设T为 的子树， 是T中的所有结点， 是T中的所有边，如果把T的结点分成两个簇，T有如下性质： 。由于只保留了结点的最大跟随度，故而 的边数少于n-1，实现了对原始网络的简化。在简化后的网络中可以看出具有社区最大领导度的结点在划分的社区中作为核心结点呈现，故而符合了前面提到的核心结点是领导度大的结点，而边缘结点则是跟随度比较大，跟随核心结点，边的权重反则映了一个结点对社区的隶属度。简化后的网络是一个树结构类型，而每一个社区可以看作是简化了的网络中的一个子树，每个树可以分为树根和叶子也就是代表这网络中的核心结点和边缘结点。对于原始网络边缘结点与核心结点间可能存在多条边，而简化后的边结点与核心结点相只有一条边连接，因而对于简化后的网络进行社区划分则大大减小的划分的复杂度。

基于簡化过的网络 ，利用社区间联系稀疏的性质，即存在的公共边最少原理进行社区检测，具体公式为：

min[Δ ]

其中 是对V的划分， 是指第l个划分社区，k是划分社区的个数。根据属性四可以得出：

因此最小化Δ（ ），即可得到社区划分，从 中删除具有第一个k-1最低权重的边，以找出k个社区。

3实验分析

3.1实验环境与数据

本实验在三个数据集上进行实验验证。数据集利用爬虫获取微博平台上的数据包括152个用户，用户的3497条评论信息以及这152个用户间的网络结构，其中涉及4个社区结构;在淘宝平台上获取了276个用户，5796条评论信息以及这些用户间存在的网络结构信息，其中包含9个社区结构;在京东平台上获取214个用户的5327条商品评论信息以及网络结构信息，其中包含6个社区结构。实验环境如下：处理器为 Core i7-6500U @ 2.50GHz，运行内存8.0 GB，Windows 10操作系统，开发工具为python 3.6。

3.2评估方法

实验采用的评价方法为模块度度量Q、归一化互信息（NMI）。

1）采用模块度Q进行社区划分的内部度量。模块度Q是由Newman等人提出的用于社区检测算法中以检测社区内部结构稳定性的一个衡量指标，表示复杂网络社区划分的结果是否合理，社区划分内部是否连接紧密，定义为：

其中E为网络中总边数， 为网络的邻接矩阵， 表示结点i的度， 为结点i所属的社区，其取值越大表示社区划分的质量好，社区越稳定。

2）NMI度量计算社区检测结果与社区的真实划分类别间的互信息，可以用来评价社区划分类别标志一致性的高低，表示为：

其中n为社区中结点的个数， 表示社区中公共结点的个数。NMI的计算结果值位于[0，1]之间，NMI值越高则表示社区检测结果越良好，反之检测结果越差。

3.3实验结果与分析

（a）、（b）、（c）分别表示本文算法在三个数据集上的社区划分结果。从图中可以看出本文提出的算法在三个数据集上都取得了良好的结果，可以很好的将用户进行社区划分，并且对于边缘结点也可以很准确的进行社区归类，不存在被误分的结点，结点划分与实际网络基本一致，社区划分结果可视化强。

可以看出在NMI评估方法下三个数据集上，本文提出的算法都取得了最好的结果。相比DPC方法，本文算法的NMI值平均提高了0.042，得到了较好的NMI值。分析原因是本文利用了用户的评论信息，并结合和用户结点的跟随度作为网络简化过程中的权重，从而可以更加紧密了用户之间的关系，而且划分网络的核心结点和边缘结点进行社区划分提高了网络中边缘结点与核心中心结点的联系，不至于出现边缘结点被遗漏的问题。而DPC算法没有考虑用户的内容属性而仅利用了网络中结点间的拓扑结构来描述用户关系，这给社区划分结果带来了一定的不准确性。而DBSCAN算法则由于其参数的选择问题也是给其聚类效果带来了一定的负面影响，使其产生了较差的聚类效果。K-means由于需要提前预知网络划分社区的个数，而没有对结点进行跟进一步的分析，只是简单划分，因此划分结果也不理想。

4总结

在本文中，我们提出了一种新的基于用户评论信息的网络简化电商平台社区发现算法。在新算法中，我们利用结点的领导度和跟随度来衡量原始网络中结点间的连接关系，并利用这两个度量和电商网络平台中用户的评论信息将原始无向无权网络映射为简化的有向加权网络，即形成加权树或森林。简化后的网络提供了对社区结构非常直观的理解和可解释性，在此基础上，提出用截断树枝的方法进行社区的划分。在实验分析中将本文提出的算法与其他三种社区检测算法进行了比较，结果表明本文提出的算法对于网络的可视化是非常有效的，并且社区划分结果的准确率也很高，能更好地划分网络，实用价值较高。

参考文献

费蓉，李莎莎，胡博，唐瑜，方金正.基于标签传播的拓扑势社区检测算法[J].计算机系统应用，2020，29（10）：148-157.

作者单位

西安工程大学 计算机科学学院，陕西 西安 710048