开放科学（资源服务）标志码（OSID）：

0 概述

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

1 相关工作 1.1 个人社交网络特征分析

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

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

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、概率因子P_E、雌雄蜘蛛数目N_f和N_m，计算公式如下：

$ \left\{\begin{array}{l}{N}_{\mathrm{f}}=\mathrm{f}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{r}\left[\right(0.9-\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\cdot 0.25)\cdot N]\\ {N}_{\mathrm{m}}=N-{N}_{\mathrm{f}}\end{array}\right. $

(1)

其中：floor()表示向下取整；rand表示[0, 1]中的随机数，随机产生雌雄种群的计算公式如下：

$ \left\{\begin{array}{l}{F}_{ij}={F}_{j\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}({F}_{j\mathrm{m}\mathrm{a}\mathrm{x}}-{F}_{j\mathrm{m}\mathrm{i}\mathrm{n}})\\ {M}_{kj}={M}_{j\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}({M}_{j\mathrm{m}\mathrm{a}\mathrm{x}}-{M}_{j\mathrm{m}\mathrm{i}\mathrm{n}})\end{array}\right. $

(2)

其中：F和M分别表示雌性和雄性种群；S表示所有种群且$ S=F\bigcup M $；F_jmax和F_jmin分别表示第j维的上限和下限，i∈{1，2，…，N_f}，k∈{1，2，…，N_m}，j∈{1，2，…，N}。

1.3.2 蜘蛛个体振动协作学习

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

$ {F}^{t+1}=\left\{\begin{array}{l}{F}_{i}^{t}+\alpha \mathrm{V}\mathrm{i}{\mathrm{b}}_{ci}({S}_{\mathrm{c}}-{F}_{i}^{t})+\beta \mathrm{V}\mathrm{i}{\mathrm{b}}_{bi}({S}_{\mathrm{b}}-{F}_{i}^{t})+\\ \delta (\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}-0.5), {r}_{\mathrm{m}}\le {P}_{\mathrm{E}}\\ {F}_{i}^{t}-\alpha \mathrm{V}\mathrm{i}{\mathrm{b}}_{ci}({S}_{\mathrm{c}}-{F}_{i}^{t})-\beta \mathrm{V}\mathrm{i}{\mathrm{b}}_{bi}({S}_{\mathrm{b}}-{F}_{i}^{t})+\\ \delta (\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}-0.5), \mathrm{其}\mathrm{他}\end{array}\right. $

(3)

其中：$ \mathrm{V}\mathrm{i}{\mathrm{b}}_{ci} $、$ \mathrm{V}\mathrm{i}{\mathrm{b}}_{bi} $表示个体i对个体c、b的震动感知能力；r_m为雌性个体的婚配半径。

$ \mathrm{V}\mathrm{i}{\mathrm{b}}_{vl}={\omega }_{l}{\mathrm{e}}^{-{d}_{vl}^{2}}, {d}_{vl}=‖{S}_{v}-{S}_{l}‖ $

(4)

$ {\omega }_{l}=\left\{\begin{array}{l}1-\frac{J\left({S}_{l}\right)-\mathrm{m}\mathrm{i}\mathrm{n}J\left({S}_{l}\right)}{\mathrm{m}\mathrm{a}\mathrm{x}J\left({S}_{l}\right)-\mathrm{m}\mathrm{i}\mathrm{n}J\left({S}_{l}\right)}, \mathrm{M}\mathrm{a}\mathrm{x}\\ \frac{J\left({S}_{l}\right)-\mathrm{m}\mathrm{a}\mathrm{x}J\left({S}_{l}\right)}{\mathrm{m}\mathrm{i}\mathrm{n}J\left({S}_{l}\right)-\mathrm{m}\mathrm{a}\mathrm{x}J\left({S}_{l}\right)}, \mathrm{M}\mathrm{i}\mathrm{n}\end{array}\right. $

(5)

其中：Max表示最大化问题的取值；Min表示最小化问题的取值；t表示当前迭代次数；r_m、α、β、δ表示在[0, 1]中的随机数；l∈{1，2，…，N}；S_c表示距离F_i最近且优于自身的个体；S_b表示雌性种群中的最优个体；Vib_vl表示个体l对个体v的振动感知能力；J(S_l)表示个体S_l的目标函数适应度值；d_vl表示个体v与个体l的欧氏距离。

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

$ {M}^{t+1}=\left\{\begin{array}{l}{M}_{i}^{t}+\alpha \mathrm{V}\mathrm{i}{\mathrm{b}}_{fi}({S}_{f}-{M}_{i}^{t})+\delta (\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}-0.5), {\omega }_{{N}_{\mathrm{f}+i}}\ge {\omega }_{{N}_{\mathrm{f}+\mathrm{m}}}\\ {M}_{i}^{t}+\alpha \left(\frac{\sum\limits_{h=1}^{{N}_{\mathrm{m}}}{M}_{h}^{t}{\omega }_{{N}_{\mathrm{f}+i}}}{\sum\limits_{h=1}^{{N}_{\mathrm{m}}}{\omega }_{{N}_{\mathrm{f}+i}}}-{M}_{i}^{t}\right), \mathrm{其}\mathrm{他}\end{array}\right. $

(6)

其中：$ {\omega }_{{N}_{\mathrm{f}+\mathrm{m}}} $表示处于中间位置的权值，雄性个体按权值降序排列，若大于等于中间位置的权值的雄性，则按支配个体更新，否则按非支配个体更新；S_f表示距离M_i最近的个体；$ \sum\limits_{h=1}^{{N}_{\mathrm{m}}}{M}_{h}^{t}{\omega }_{{N}_{\mathrm{f}+i}}/\sum\limits_{h=1}^{{N}_{\mathrm{m}}}{\omega }_{{N}_{\mathrm{f}+i}} $表示雄性蜘蛛的平均权值。

1.3.3 婚配选择

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

$ {P}_{q}=\frac{{w}_{q}}{\sum\limits_{q\in {T}_{g, i}}{w}_{g}} $

(7)

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

$ r=\sum\limits_{j=1}^{N}({P}_{j}^{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}-{P}_{j}^{\mathrm{l}\mathrm{o}\mathrm{w}})/2N $

(8)

其中：$ {P}_{j}^{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}} $和$ {P}_{j}^{\mathrm{l}\mathrm{o}\mathrm{w}} $分别为第j维的概率上限和下限。

2 个人社交网络社区发现算法 2.1 基于群智能蜘蛛算法的社区发现

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

2.2 邻边属性相似

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

定义1   假设$ {G}_{u}=({V}_{u}, {E}_{u}) $是个人$ u $所属的社交网络，其中$ {V}_{u}={N}_{u}^{+} $和$ {E}_{u}=\left\{\right(u, v\left)\right|u, v\in {N}_{u}^{+}\} $分别表示$ u $所属社交网络的节点集合和边集合，基于边属性相似的个人社交网络社区划分计算公式如下：

$ {C}^{e}=\left\{{C}_{k}^{e}\right|\mathrm{S}\mathrm{i}\mathrm{m}({e}_{ij}, {e}_{uv})>{\theta }_{k}, \forall {e}_{ij}, {e}_{uv}\in {C}_{k}^{e}\} $

(9)

其中，$ {C}^{e} $为社区划分，$ {\theta }_{k} $是边相似控制系数，$ {e}_{ij} $和$ {e}_{uv} $分别表示网络中的两条边，$ \mathrm{S}\mathrm{i}\mathrm{m}({e}_{ij}, {e}_{uv})\in \left[\mathrm{0, 1}\right] $。两条边越相似在社区划分时被分配到同一社区的概率越大，即同一社区内部连接的边密度相比社区间连接的边密度更大^[2]。

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

$ \begin{array}{l}\mathrm{S}\mathrm{i}\mathrm{m}({e}_{ij}, {e}_{uv})=\mathrm{e}\mathrm{x}\mathrm{p}\left({w}_{\mathrm{t}}\cdot \mathrm{S}\mathrm{i}{\mathrm{m}}_{\mathrm{t}}({e}_{ij}, {e}_{uv})+{w}_{\mathrm{p}}\cdot \mathrm{S}\mathrm{i}{\mathrm{m}}_{\mathrm{p}}({e}_{ij}, {e}_{uv})\right)\mathrm{ }\cdot \\ {\left(1+\mathrm{e}\mathrm{x}\mathrm{p}\left({w}_{\mathrm{t}}\cdot \mathrm{S}\mathrm{i}{\mathrm{m}}_{\mathrm{t}}({e}_{ij}, {e}_{uv})+{w}_{\mathrm{p}}\cdot \mathrm{S}\mathrm{i}{\mathrm{m}}_{\mathrm{p}}({e}_{ij}, {e}_{uv})\right)\right)}^{-1}\end{array} $

(10)

其中：$ {w}_{\mathrm{t}} $和$ {w}_{\mathrm{p}} $分别表示网络边结构相似和边属性相似的控制权值；$ \mathrm{S}\mathrm{i}{\mathrm{m}}_{\mathrm{t}}({e}_{ij}, {e}_{uv}) $和$ \mathrm{S}\mathrm{i}{\mathrm{m}}_{\mathrm{p}}({e}_{ij}, {e}_{uv}) $分别表示两条边$ {e}_{ij} $、$ {e}_{uv} $在网络结构和属性上的相似度值。

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

$ \mathrm{S}\mathrm{i}{\mathrm{m}}_{t}({e}_{ij}, {e}_{uv})=\\ \left\{\begin{array}{l}0, i\ne u\mathrm{且}j\ne v\\ \xi \times \frac{\left|{N}_{i}\bigcap {N}_{u}\right|}{\left|{N}_{i}\bigcup {N}_{u}\right|}+\frac{2(1-\xi )\times \left|E({N}_{i}\bigcap {N}_{u})\right|}{\left|{N}_{i}\bigcap {N}_{u}\right|\times \left(\left|{N}_{i}\bigcap {N}_{u}\right|-1\right)}, i\ne u\\ \xi \times \frac{\left|{N}_{j}\bigcap {N}_{v}\right|}{\left|{N}_{j}\bigcup {N}_{v}\right|}+\frac{2(1-\xi )\times \left|E({N}_{j}\bigcap {N}_{v})\right|}{\left|{N}_{j}\bigcap {N}_{v}\right|\times \left(\left|{N}_{j}\bigcap {N}_{v}\right|-1\right)}, j\ne v\end{array}\right. $

(11)

其中：$ {N}_{i} $表示连接节点i的边集合；$ E({N}_{i}\bigcap {N}_{u}) $表示节点i和v公共的邻边集合；$ \xi \in \left[\mathrm{0, 1}\right] $表示边结构控制系数，当$ \xi $=1时类似于文献[8]，仅考虑边的JACCARD相似，当$ \xi \ne 1 $时兼顾邻边对边相似所起的作用。若各条边两端节点间公共的邻边越多，则表示边结构越相似。

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

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

$ {\mathit {\boldsymbol{{P}}}}_{{e}_{uv}}={P}_{u}\oplus {P}_{v} $

(12)

其中：$ {\mathit {\boldsymbol{{P}}}}_{{e}_{uv}} $表示边$ {e}_{uv} $的属性向量；$ \oplus $表示and运算；$ {P}_{u}\mathrm{和}{P}_{v} $分别表示边$ {e}_{uv} $的两端节点u和v的属性集合，边$ {e}_{uv} $的第$ k $个($ k $小于节点属性最大个数)属性值为$ {\mathit {\boldsymbol{{P}}}}_{{e}_{uv}}={P}_{u}\left(k\right)\wedge {P}_{v}\left(k\right) $，若$ {P}_{u}\left(k\right) $和$ {P}_{v}\left(k\right) $同时为1，则$ {\mathit {\boldsymbol{{P}}}}_{{e}_{uv}} $为1，否则为0，若两个节点相同的属性数越多，则$ {\mathit {\boldsymbol{{P}}}}_{{e}_{uv}} $值越大。

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

$ \mathrm{S}\mathrm{i}{\mathrm{m}}_{p}({e}_{ij}, {e}_{uv})=\left\{\begin{array}{l}0, i\ne u\mathrm{且}j\ne v\\ \frac{\mathrm{n}\mathrm{u}{\mathrm{m}}_{1}({\mathit{\boldsymbol{{P}}}}_{{e}_{ij}}\wedge {\mathit{\boldsymbol{{P}}}}_{{e}_{uv}})}{\mathrm{n}\mathrm{u}{\mathrm{m}}_{1}({\mathit{\boldsymbol{{P}}}}_{{e}_{ij}}\vee {\mathit{\boldsymbol{{P}}}}_{{e}_{uv}})}, \mathrm{其}\mathrm{他}\end{array}\right. $

(13)

其中：$ \mathrm{n}\mathrm{u}{\mathrm{m}}_{1}\left(\mathrm{ }\right) $表示属性向量的值为1的数量总和。

2.3 模块度增量判定条件

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

$ {Q}_{\mathrm{w}}=\sum\limits_{i, j}\left[\frac{{W}_{ij}}{2{m}_{\mathrm{w}}}-\frac{{d}_{\mathrm{w}}\left(i\right)}{2{m}_{\mathrm{w}}}\cdot \frac{{d}_{\mathrm{w}}\left(j\right)}{2{m}_{w}}\right]\cdot \delta ({c}_{i}, {c}_{j}) $

(14)

其中：$ {W}_{ij} $表示边$ {E}_{ij} $的权值；$ {d}_{\mathrm{w}}\left(i\right) $表示与节点$ i $连接边的权值和；$ {m}_{\mathrm{w}}=\sum\limits_{ij}{W}_{ij}/2 $表示网络中所有连接边的权值总和；c_i、c_j分别表示两个社区内部的所有节点。若节点$ i $和$ j $属于同一个社区则$ \delta ({c}_{i}, {c}_{j}) $=1，否则$ \delta ({c}_{i}, {c}_{j}) $=0。若一条含节点$ i $的边从自身所属社区$ {C}_{x} $合并到另一个社区$ {C}_{y} $，则社区的模块度增量计算公式如下：

$ \begin{array}{l}\mathrm{\Delta }{Q}_{\mathrm{w}}(i, {C}_{x}, {C}_{y})=\left[\frac{{d}_{\mathrm{w}}^{y}\left(i\right)}{2{m}_{\mathrm{w}}}-\frac{2{Z}_{\mathrm{t}\mathrm{o}\mathrm{t}}^{y}+{d}_{\mathrm{w}}\left(i\right)}{2{m}_{\mathrm{w}}}\cdot \frac{{d}_{\mathrm{w}}\left(i\right)}{2{m}_{\mathrm{w}}}\right]-\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\hspace{1em}\left[\frac{{d}_{\mathrm{w}}^{x}\left(i\right)}{2{m}_{\mathrm{w}}}-\frac{2{Z}_{\mathrm{t}\mathrm{o}\mathrm{t}}^{x}+{d}_{\mathrm{w}}\left(i\right)}{2{m}_{\mathrm{w}}}\cdot \frac{{d}_{\mathrm{w}}\left(i\right)}{2{m}_{\mathrm{w}}}\right]\end{array} $

(15)

其中：$ {d}_{\mathrm{w}}^{x}\left(i\right) $表示节点$ i $与$ {C}_{x} $之间边的权值之和；$ {Z}_{\mathrm{t}\mathrm{o}\mathrm{t}}^{x} $表示$ {C}_{x} $所有节点相关边的权值之和。

2.4 算法步骤

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

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

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

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

步骤4   按式(8)计算婚配半径。

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

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

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

2.5 算法复杂度分析

NLA/SCD算法耗时主要集中于个体的权值计算部分。假设$ {n}_{p} $为用户属性数量，$ n $为节点数，m为种群数，d_max为最大迭代次数，最多共享边为$ n{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}({d}_{\mathrm{m}\mathrm{a}\mathrm{x}}-1)/2 $，连边属性计算的时间复杂度为$ O(n{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{3}+n{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}{n}_{p}/2) $。由于SSO算法为分散寻优，种群迭代的时间复杂度约为$ O\left(n{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{}\right) $，因此NLA/SCD算法理想状态的时间复杂度约为$ O(m{n}_{p}+n{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}) $。

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^® Core^TM 2 Q9550 @ 2.83 GHz、8 GB内存。社区划分的评价指标为模块度和标准化互信息(Normalized Mutual Information，NMI)^[16]。NLA/SCD算法最佳参数设置如表 2所示。

3.1 参数设置实验

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

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

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算法相比另外两种算法更稳定且耗时更少。

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

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

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

4 结束语

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