一种融合邻边属性的个人社交网络社区发现算法

李有红，王学军，谌裕勇，赵跃龙，徐文贤，3

（1.广东工业大学华立学院舆情大数据中心，广州511325；2.华南理工大学计算机科学与工程学院，广州510006；3.华南师范大学图书馆，广州510631）

0 概述

随着信息技术的快速发展以及互联网络应用的日益普及，社交网络中的交互关系呈现出多样化发展趋势。社区是社交网络中一种典型的隐形中观结构［1-3］，利用社区发现方法识别个人社交网络［4-5］中的社区，可实现最大限度的资源共享、咨询决策和信息服务等功能，利用社交数据构建智能化的社交电商系统已成为当今知识发现领域的研究热点。在个人社交网络中，边是结构的支撑，节点的属性是网络多样性的重要延伸，因此边和属性的权重、时效、密集程度等多模特征演化都可能会导致社区结构的重构。在社交网络中，两条边的公共邻边（与两条边各自节点相连的边）越多，邻边和节点在同一社交圈的可能性越大。本文在融合邻边结构及其节点属性相似特性的基础上，利用差分进化的群体智能社会蜘蛛优化（Social Spider Optimization，SSO）算法寻求最佳的个人社区结构划分，并提出融合邻边属性的群智能个人社交网络社区发现算法NLA/SCD。

1 相关工作

1.1 个人社交网络特征分析

在个人社交网络中，边和属性的权重、时效、密集程度等多模特征演化可能会导致社区结构的重构。如图1所示，在现实世界中，一个以个人亲属关系、同学关系等组成的社交网络圈随着用户个人的地理位置、兴趣爱好、研究方向等内在因素（节点属性）的变化，网络结构也会发生变化。

图1 带有社区标记的个人社交网络Fig.1 Personal social network with community flags

在社交网络结构中，两条边的公共邻边越多，邻边和节点在同一社交圈的可能性就越大。如图2所示，边1 和边9 存在邻边3 和邻边8，因此边1 和边9就可能属于同一个社区。在微信社交圈中，如果用户朋友的朋友之间相互认识，那么两个用户各自的朋友在一个社交圈的概率就很大。边1 的邻边有边2、边3、边4、边6、边7 和边8，其中边5 和边9 虽然不是边1 的邻边也不相连，但是分别都与边1 的两个或以上邻边相连，因此可认为边5 和边9 与边1 的相似程度非常高，它们和各自的节点属于同一社区。

图2 边结构相似示意图Fig.2 Schematic diagram of edge structural similarity

1.2 基于结构和属性的社区发现

目前，关于个人社交网络的社区发现研究主要包括基于拓扑结构的划分［2］和基于主题内容的划分［6］两个方面。拓扑结构是网络关系的支撑，用户通过各种长期的交互关系建立稳定的社交圈。由于个人社交网络社区具有高度的重叠特性，因此基于边结构的社区划分方法成为近年来的研究热点。文献［7］根据用户朋友关系，提出一种基于边的个人社交网络社区发现模型，并将其应用于物联网络优化中。文献［4］根据用户邻近关系，采用k-近邻方法划分社交网络，但该方法中k的取值是影响社区划分结果的关键，k值越大噪声越多，k值越小可供参考的邻边信息越少，社区划分精度越低。文献［5］指出若邻节点重叠比例高，则节点相似度高，并设计基于邻节点重叠比例的社区划分方法。文献［8］将节点轮廓和网络结构相结合，设计边轮廓的增强链接聚类算法ELC 用于社交圈识别。基于主题内容的方法主要是将用户主题属性与内容关系强度相结合。文献［9］基于微博中的个人局部属性特征，设计模块函数，利用贪婪算法优化社团划分。文献［10］基于社交网络语义评分提出局部子网边权重加权策略并构建SNTOCD 算法，在挖掘兴趣子群和语义主题方面取得了较好的效果，但该算法仍存在过早收敛的问题。文献［6］将边结构和节点属性相似相结合，提出一种扩展属性的个人社交网络发现算法CESNA，在规模较大且存在噪声的情况下，检测准确度和扩展性均有所提升，但在个人社交网络环境中仍存在适应性较差的问题。

1.3 群智能蜘蛛算法

社会蜘蛛优化算法［11］是一种优化的群体智能进化算法，将对象初始化为雌雄蜘蛛，模仿蜘蛛的社会行为。在社会蜘蛛优化算法中，通过雌雄个体差分化的个体振动协作学习、婚配（杂交）等行为进行繁衍优化，快速高效地探索空间解集（最优目标解集）。社会蜘蛛优化算法可从局部和全局角度优化寻优过程，较好地保持种群多样性，避免寻优过程过早收敛［11-12］。

1.3.1 种群初始化

初始化相关参数为种群数目N、概率因子PE、雌雄蜘蛛数目Nf和Nm，计算公式如下：

其中：floor（）表示向下取整；rand 表示［0，1］中的随机数，随机产生雌雄种群的计算公式如下：

其中：F和M分别表示雌性和雄性种群；S表示所有种群且S=F∪M；Fjmax和Fjmin分别表示第j维的上限和下限，i∈｛1，2，…，Nf｝，k∈｛1，2，…，Nm｝，j∈｛1，2，…，N｝。

1.3.2 蜘蛛个体振动协作学习

雌性个体通过震动进行吸引或排斥其他个体，雌性蜘蛛分为两类进行个体更新，若小于等于概率因子PE则为吸引，反之为排斥。Fi个体的更新方式如下：

其中：Vibci、Vibbi表示个体i对个体c、b的震动感知能力；rm为雌性个体的婚配半径。

其中：Max 表示最大化问题的取值；Min 表示最小化问题的取值；t表示当前迭代次数；rm、α、β、δ表示在［0，1］中的随机数；l∈｛1，2，…，N｝；Sc表示距离Fi最近且优于自身的个体；Sb表示雌性种群中的最优个体；Vibvl表示个体l对个体v的振动感知能力；J（Sl）表示个体Sl的目标函数适应度值；dvl表示个体v与个体l的欧氏距离。

雄性蜘蛛的个体更新按种群适应度大小排序，可分为支配和非支配两种情况，支配个体具有较强的吸引异性靠拢的能力，而非支配个体则有向雄性中间个体聚集的能力。Mi个体的更新方式如下：

1.3.3 婚配选择

雌雄蜘蛛经过逐代更新后，婚配产生新个体替换劣质蜘蛛，直到满足条件为止。对于处于支配的雄性，将按轮盘赌注方式选择婚配半径r内的雌性组成新的个体Snew，即dik≤r，i∈Tg，k，k=（1，2，…，D），其中D为雄性支配个体的总数。若J（Snew）的适应度值优于种群中的最差个体，则用Snew替换它在雄性个体i婚配半径内的全部雌性个体并标记为子种群Tg，i，在Tg，i内雌性个体q被雄性个体i选择婚配的概率为Pq，计算公式如下：

婚配半径r的计算公式如下：

2 个人社交网络社区发现算法

2.1 基于群智能蜘蛛算法的社区发现

基于群体智能进化算法的社区发现通常是将社区划分质量增量作为进化筛选条件，以局部节点相似或聚集系数等值作为进化算法种群的适应度函数值［12-14］，若算法收敛则社区划分结束。为提高社交网络社区发现的适应度值，本文将网络连接边、邻边属性相似和基于边的模块度增量分别作为蜘蛛种群、适应度函数和进化停止条件，设计NLA/SCD 算法，NLA/SCD 算法流程如图3所示。

图3 NLA/SCD 算法流程Fig.3 Procedure of NLA/SCD algorithm

2.2 邻边属性相似

本文以个人社交网络中连接边为研究对象，将社区发现问题转换为网络边及其属性相似的聚类问题。

定义1假设Gu=(Vu,Eu)是个人u所属的社交网络，其中和分别表示u所属社交网络的节点集合和边集合，基于边属性相似的个人社交网络社区划分计算公式如下：

其中，Ce为社区划分，θk是边相似控制系数，eij和euv分别表示网络中的两条边，Sim(eij,euv)∈[0,1]。两条边越相似在社区划分时被分配到同一社区的概率越大，即同一社区内部连接的边密度相比社区间连接的边密度更大［2］。

定义2通过边相似控制系数对节点结构和属性进行聚类来表示邻边属性相似，计算公式如下：

其中：wt和wp分别表示网络边结构相似和边属性相似的控制权值；Simt(eij,euv)和Simp(eij,euv)分别表示两条边eij、euv在网络结构和属性上的相似度值。

定义3在JACCARD 边结构相似的基础上，结合邻节点关系和公共邻边来表示邻边结构相似，计算公式如下：

其中：Ni表示连接节点i的边集合；E(Ni∩Nu)表示节点i和v公共的邻边集合；ξ∈[0,1]表示边结构控制系数，当ξ=1 时类似于文献［8］，仅考虑边的JACCARD相似，当ξ≠1 时兼顾邻边对边相似所起的作用。若各条边两端节点间公共的邻边越多，则表示边结构越相似。

在社交网络中，除了用户间的关注或被关注关系外，兴趣属性、意见属性和所属地域属性等因素都会与社区形成和演化有关，因此在社区划分时需要对边的属性进行拟合。

定义4节点属性向量表示将相邻多个节点的属性相关联，其中边的属性由连接边节点的属性共同决定，即由该边两端节点的所有属性进行and 运算组合，计算公式如下：

定义5通过边中属性相同的个数与边属性总数比来表示边属性相似，计算公式如下：

其中：num1()表示属性向量的值为1 的数量总和。

2.3 模块度增量判定条件

基于SSO 算法的群体智能社区划分的本质是最大化模块度问题。在SSO 算法的优化过程中，以边为个体的更新与婚配，保证了局部的社区优化。种群的每一代婚配都能产生社区划分模块度增量，当连续几代边合并为社区且模块度增量不发生明显变化时算法停止，因此引入基于边的模块度增量模型［15］，模块度计算公式如下：

其中：Wij表示边Eij的权值；dw(i)表示与节点i连接边的权值和；表示网络中所有连接边的权值总和；ci、cj分别表示两个社区内部的所有节点。若节点i和j属于同一个社区则δ(ci,cj)=1，否则δ(ci,cj)=0。若一条含节点i的边从自身所属社区Cx合并到另一个社区Cy，则社区的模块度增量计算公式如下：

2.4 算法步骤

NLA/SCD 算法的具体步骤如下：

步骤1种群初始化。将社交网络用户连接边初始化为蜘蛛种群，种群规模N，概率因子PE，最大迭代次数max（t），按式（1）初始化Nf和Nm；按式（2）初始化蜘蛛雌雄种群S、F和M。

步骤2按式（10）计算个体的相似权值并排序。

步骤3按式（3）和式（6）更新雌雄蜘蛛种群。

步骤4按式（8）计算婚配半径。

步骤5先对支配雄性个体婚配并对其婚配半径内的雌性按式（7）的选择概率以轮盘赌注方式进行婚配，再替换最差个体。

步骤6若模块度增量连续几代都不增加，则退出进化，否则转到步骤2。

步骤7将收敛后的种群标签映射为社区。

2.5 算法复杂度分析

NLA/SCD 算法耗时主要集中于个体的权值计算部分。假设np为用户属性数量，n为节点数，m为种群数，dmax为最大迭代次数，最多共享边为ndmax(dmax-1)/2，连边属性计算的时间复杂度为。由于SSO 算法为分散寻优，种群迭代的时间复杂度约为O(ndmax)，因此NLA/SCD算法理想状态的时间复杂度约为。

3 实验与结果分析

为验证NLA/SCD 算法的有效性，本文主要进行3 组实验：1）获取边结构相似中控制系数的最佳值；2）验证SSO 算法的连边属性社区发现的改进效果；3）比较NLA/SCD 算法与传统智能进化社区发现算法的划分精度。在Karate［16］、Dolphins［16］、ego-Facebook［17］和ego-Twitter［17］这4 个不同规模的网络数据集上进行实验，如表1所示。实验运行平台为Windows 7 企业版64 bit 操作系统、CPU Intel®CoreTM2 Q9550 ＠ 2.83 GHz、8 GB 内存。社区划分的评价指标为模块度和标准化互信息（Normalized Mutual Information，NMI）［16］。NLA/SCD 算法最佳参数设置如表2所示。

表1 网络数据集Table 1 Network datasets

表2 NLA/SCD 算法最佳参数设置Table 2 Optimal parameters setting of NLA/SCD algorithm

3.1 参数设置实验

实验采用斯坦福大学个人社交网络数据集ego-Facebook，以个人社交圈网络节点数为变量进行检测，3 组不同规模的网络节点数分别为59、227 和792，所有参数值取10 次实验的平均值，验证边结构控制系数ξ对划分精度的影响。如图4所示，当边结构控制系数ξ取0.5～0.7 时，本文算法在3 个网络数据集中均具有较好的表现，因此在下文实验中设置ξ=0.7。

图4 边结构相似控制系数与NMI 的关系Fig.4 The relationship between edge structure similarity control coefficient and NMI

在ego-Facebook 数据集上的网络节点数为59、种群规模为500，wt+wp=1，Wt初始阈值设置参考文献［14］，在NLA/SCD 算法中，将各项参数阈值从0 到1 进行调整测试来分析NMI 的变化情况。如图5所示，在ego-Facebook 数据集中个人社交网络边结构相似权值wt对网络划分精度具有较大影响，且边属性相似权值wp也会影响社区划分结果，而概率因子PE设置与SSO算法［11］接近时效果最佳，通过参数设置实验验证了表2 理论最佳参数设置的正确性与有效性。

图5 NLA/SCD 参数设置对NMI 的影响Fig.5 The influence of parameters setting on NMI in NLA/SCD

3.2 边和属性社区发现实验

实验采用斯坦福大学个人社交网络数据集ego-Facebook，对比算法为通过节点间连接和节点属性相似的社交网络发现算法M-L［18］和增强链聚类算法ELC［8］。以个人社交圈节点数为变量进行实验，所有参数值取10 次实验的平均值。M-L、ELC 和NLA/SCD 算法均为基于网络边和属性的社区发现算法。M-L 算法采用节点属性相似计算方法，EML 与NLA/SCD 算法采用相似的属性策略，不同的是NLA/SCD算法运行在SSO 算法框架上。由于本文将连边属性作为SSO 算法的适应度函数，因此在每一代结束后将社区模块度增量作为判断准则，此类多层次和多粒度的设计可有效避免模块度优化而分辨率限制［6］问题，对算法精度的提升起到关键作用，如图6（a）所示。3 种算法随着节点数的增加，模块度和NMI 值均有所下降，但NLA/SCD 算法由于结合了边的属性特征，采用SSO 差分寻优策略使得算法划分精度相对稳定。如图6（b）所示，由于SSO 算法在进化第2 代时存在振荡期，因此当节点数在547 时会稍有影响，但SSO 算法经过3 代或4 代进化后能够快速根据差分学习策略进行自适应调整，达到较高的划分精度。其主要原因为在NMI 测试时因为算法终止判定与NMI 值不直接相关，所以节点数增加对NLA/SCD算法影响较小。基于SSO 的蜘蛛种群按雌雄差分进化，从多路寻找最优解，构建与适应度函数有关的半径婚配算子，并逐代吞并劣质个体，从而加快算法收敛。如图6（c）所示，在ego-Facebook 中通过不断增加节点数测试算法达到最佳划分精度的收敛时间，可以看出NLA/SCD 算法相比另外两种算法更稳定且耗时更少。

图6 3 种个人社交网络发现算法的性能比较Fig.6 Performance comparison of three personal social network discovery algorithms

3.3 社区发现算法性能比较实验

实验网络数据集为Karate 和Dolphins 社会网络数据集以及ego-Facebook 和ego-Twitter 个人社交网络数据集。对比算法为经典社区发现算法GA-Net［19］、隔代遗传算法GGA+［13］、启发式差分搜索算法HDSA［20］（这3 种算法是近几年提出的社区划分精度较高的群智能社区发现算法）、增强链聚类算法ELC［8］、扩展属性的个人社交网络发现算法CESNA［6］以及基于局部节点相似的群集蜘蛛差分进化社区发现算法DESSO/DC［14］。各算法参数值均采用最佳值，在同等规模数据集上进行实验，模块度比较如表3所示。

表3 7 种社区发现算法的模块度比较Table 3 Modularity comparison of seven community discovery algorithms

可以看出，群智能社区发现算法在个人社交网络划分方面仍存在一定的适应性问题，导致划分精度不高，而边和属性相结合的社区发现算法在寻优精度方面更具优势。NLA/SCD 算法通过差分进化方式，采用局部和全局兼顾的混合学习设计，并利用婚配择优的算子策略保证种群的多样性，相比GA-Net、GGA+算法的进化算子更多样，相比HDSA算法的算子排序可随雌雄种群进一步差别化，适应性更强。另外，NLA/SCD 算法采用加权的模块度增量算子择优准则，可更有效地判断社区划分效果。可见，与现有群智能社区发现算法相比，NLA/SCD算法社区划分精度更高，而且本文的适应度函数和算子择优准则均是针对个人社交圈进行设计，因此在检验个人社交网络社区划分时效果更佳。

4 结束语

本文以个人社交网络作为研究对象，在结合网络边拓扑结构和节点属性的基础上，利用社会蜘蛛优化算法寻求最佳的个人社区结构划分，提出一种基于邻边属性群智能聚类的个人社交网络社区发现算法NLA/SCD。该算法以个人社交网络的边作为SSO 算法的种群，以个体为中心逐步对边进行聚类，并且利用适应度函数和算子择优准则反映个人社交网络的真实社区划分情况。实验结果表明，该算法能保持网络社区的多样性，在参数依赖性、划分精度、运行时间和适应性等方面都有较好的性能提升。后续将针对电商消费数据，利用NLA/SCD 算法挖掘并划分其潜在的交易关系、兴趣关系和客户关系等社交关系社区，为用户提供更精准的决策信息。