网络形式背景下的社区划分方法研究

刘文星，范 敏+，李金海

1.昆明理工大学 数据科学研究中心，昆明 650500

2.昆明理工大学 理学院，昆明 650500

社会网络分析（social network analysis，SNA）起源于物理学中的适应性网络。通过研究网络关系及其结构，有助于把个体间相互关系即“微观”网络与大规模的社会系统的“宏观”结构相结合，从而得到一些有意义的概念、模式和分析结果。近年来，把复杂网络分析技术、社会网络分析理论与图论以及社会学、心理学、人类学、数学、通信科学等领域相结合，逐步发展成一个非常有潜力的研究分支。它在许多方面获得了重要的研究成果，比如：生物社区研究、传染病网络研究、城市化研究、网络经济体系研究等。

社会网络分析中的社区划分是从网络中获取概念、模式的基础，也是社会网络分析研究中的重点。现有的社会网络社区划分的研究主要集中在分布式算法设计、有先验信息的划分算法设计、模糊结构社区划分和进化网络划分等方面。文献[1]提出了一种分布式局部搜索算法，该算法是以顶点为中心的计算模型，采用了分布式图着色策略来区分相邻节点。文献[2]提出了一种基于信息熵的划分方法，并运用模拟退火算法，引入了一个新的定义，即超边切分、微切割。文献[3]主要通过构造特征矩阵和网络中的先验内容信息提出了一种基于半监督矩阵分解和随机游走的算法。文献[4]通过对网络的拟合，提出了一种新的假设检验框架，能够自动确定各种网络中的社区数量，并且快速检测模拟网络和实际网络中的社区结构。文献[5]设计了一种新的链路预测策略，能够划分具有模糊社区结构的网络。文献[6]给出了一种基于惩罚矩阵分解的复杂网络社区结构发现算法。文献[7]利用模糊粗糙方法检测进化网络中的重叠、非重叠和内在社区。以上研究各有特色，但是均未考虑网络节点自身具有的一些属性特征。

形式背景下的概念认知学习是一个新兴的交叉研究领域，它由形式概念分析、粗糙集、粒计算和认知计算等理论融合而来。近年来，在大数据环境下的概念认知学习中表现出诸多的认知优势，也取得了许多有价值的研究成果[8-10]。比如，文献[11]提出的概念认知模型为后续进一步研究提供了参考[12]。文献[13]阐述了从多个视角研究概念认知的重要性。文献[14]讨论了概念认知系统的迭代算法。形式背景下的概念分类是进行概念认知的基础和前提。文献[15]在文献[16]的基础上设计了一个新的并行概念学习框架，以满足增量式分类任务的要求。文献[17]从属性拓扑的角度探讨了概念认知学习。文献[18]采用按类标号进行划分的方法对形式背景进行划分，并把划分后的形式背景按属性项分割。文献[19]指出形式背景拆分的方法可以采用粗糙集中等价类划分的方法来完成。现有的概念认知研究为网络上的概念认知和网络社区划分提供了坚实的理论基础。

基于上述讨论，不难发现传统的社会网络社区划分没有考虑网络节点的属性信息，而这些信息在某些方面的作用明显，因为它反映了节点的内涵与特征，对社区划分具有重要意义。而传统的形式背景下的划分，没有考虑研究对象所处的网络及其结构。因此，有必要把二者结合起来，对网络形式背景下的网络社区划分进行研究，从而使得生成的网络社区分类既能描述其网络特征，又能体现出其概念内涵特征，这对网络数据挖掘与网络概念认知具有重要的理论意义和实际应用价值。

现有研究还表明，社会网络的不同角色在网络中的地位不同。某些网络，从其中一个角色出发形成的社区更有意义。比如：营销网络中以卖家出发形成的社区就更有意义，这种特点对应着单角色网络社区划分。而有些网络中，不同角色形成的社区具有不同的含义。比如：学术网络中，引用者形成的社区和被引用者形成的社区就有不同的含义，这种特点对应着双角色网络社区划分。同时某些作者引用别人和被别人引用都比较多，那么综合这两种角色形成的学术活跃度相似社区也能够被刻画出来。因此，在进行网络社区划分之前，先应该区分该网络的特点：适用于单角色网络社区划分还是双角色网络社区划分。在此基础上，结合网络结构和节点属性对网络进行社区划分，这将使得网络划分更高效地贴合实际情况。

文献[8]构造了网络形式背景，主要得到了网络概念等。本文将在文献[8]的基础上，把网络拓扑结构与属性相结合，对网络社区划分进行研究。

1 基础理论

本章介绍网络形式背景中的基本概念，如形式概念、节点的中心度、网络的中心势、网络社区概念，详见文献[8,20-21]。

定义1四元组(U,M,A,I)称为网络形式背景，其中U={x1,x2,…,xn}是非空有限节点集，M={M1,M2,…,Mk}是网络的结构矩阵，Mt(t=1,2,…,k) 为网络的t阶邻接矩阵,A={a1,a2,…,am} 是非空有限属性集，I={I1,I2,…,Ik,Ik+1}，I1,I2,…,Ik是笛卡儿积U×U上的二元关系，Ik+1是笛卡儿积U×A上的二元关系。约定，(xi,xj)∈Il(l=1,2,…,k)表示节点xi和xj是l阶邻接的，(xi,ap)∈Ik+1表示节点xi拥有属性ap。

表1 给出了网络形式背景的二维表。实际上，一个网络形式背景对应着一个网络。因此，如无特别说明，下文中提到的网络均指网络形式背景对应的网络。

Table 1 Network formal context (U,M,A,I)表1 网络形式背景(U,M,A,I)

定义2给定网络形式背景(U,M,A,I)，对于任意X⊆U,B⊆A，定义：

其中，X*表示X中所有对象共同拥有的属性组成的集合；B*表示拥有B中所有属性的对象组成的集合。如果X*=B且B*=X，那么称(X,B)为形式概念。

在有向图中，需要讨论网络节点的入度中心度和出度中心度。

定义3节点xi的入度中心度和出度中心度分别定义为：

其中，Jin表示与xi形成入度的节点的下标构成的集合，Jout表示与xi形成出度的节点的下标构成的集合。特别地，在无向图中，中心度记为cD(i)。

在有向图中，节点的相对中心度区分为入度相对中心度和出度相对中心度：

定义4网络的中心势定义为：

定义5对于网络形式背景(U,M,A,I)，称三元组(M,C,C*)为网络社区C的对象概念，简称为社区对象概念；同理，称为属性B对应的网络属性概念，简称为社区属性概念。(M,C,C*)、统称为网络社区概念。

此外，M={M1,M2}为网络社区概念的网络特征值，为社区概念的平均度，它表示社区概念内部平均重要度，为社区概念的平均势，它表示社区概念内部的差异程度。

(M,C,C*)中的C*可能为空，此时说明这些对象虽然能划分在同一社区，但没有共同属性。换言之，将共有算子进一步弱化成似然算子，就可以从另一个角度定义另一种网络社区概念。

其次，在有向图中，网络的中心势区分为入度中心势和出度中心势：

在有向网络中，网络社区概念的网络特征参数M 也需要区分入度和出度的情况：，。因此，网络社区概念在有向图中分为入度网络概念和出度网络概念，分别记为(Min,C,C*)、。

2 网络社区划分

本章主要从网络拓扑结构与属性相结合的角度对网络社区进行划分研究。具体地，先找到网络中度最大的节点，再找到与其相连的其他节点，并将具有一定属性相似度的相连节点划为一类。

2.1 单角色网络社区划分

定义6对象xi的k阶邻接集定义为：

它表示与对象xi有k阶邻接关系的对象构成的集合。特别地，一阶的情形记为Link(xi)。

定义7对象xi的β∈[0,1]属性相似集定义为：

它表示与对象xi有属性相似程度达到β以上的对象构成的集合。

下面给出基于网络结构与节点属性相结合的网络划分算法。

算法1基于网络结构与节点属性的单角色网络划分算法

输入：网络形式背景(U,M,A,I)和β值。

输出：划分的对象块CL。

步骤1计算网络中每个节点的出（入）度。

步骤2从出（入）度最大的节点xi开始，计算Link(xi)。

步骤3在Link(xi)中计算，令CL={Link(xi),，并删除M中的CL。

步骤4判断M中是否存在不为0 的元素，若有则返回步骤2；否则，输出CL，算法结束。未进行分类的对象，单独划为一类。

在上述算法中，步骤1 的时间复杂度为O(n)（n为网络形式背景中的对象个数），步骤2 的时间复杂度为O(n2)，步骤3 和步骤4 的时间复杂度为O(n2)，因此算法1 的时间复杂度为O(n2)。

算法1 是在单角色网络中考虑网络的出（入）度，研究网络社区划分；同样，也可以考虑在无向网络中讨论社区划分问题，只需把算法1 中节点的出（入）度替换成节点的度即可。

2.2 双角色网络社区划分

类似于2.1 节，也可以给出基于网络结构与节点属性的双角色网络划分算法。

算法2基于网络结构与节点属性的双角色网络划分算法

输入：网络形式背景(U,M,A,I)和β值。

输出：划分的对象块CL。

步骤1重复调用算法1，将其输出结果分别记为CL1和CL2，其中CL1为出度划分结果，CL2为入度划分结果。

步骤2计算网络中每个节点的度，它是入度与出度之和。

步骤3从度最大的节点xi开始，计算Link(xi)。

步骤4在Link(xi)中计算，记CL3={Link(xi),，并删除M中的CL3。

步骤5判断M中是否存在不为0 的元素，若有则返回步骤2；否则，输出CL3，算法结束。未进行分类的对象，单独划为一类。

由于算法2 与算法1 的基本步骤相同，只是同时计算了节点的入度和出度，因此算法2 的时间复杂度也为O(n2)。

3 实例分析

例1图1 是一个社交营销网络，其中x1～x10表示研究对象，xi到xj的弧表示xi将货物卖给xj。由图1可得表2 中的网络形式背景。下面利用算法1 对该网络进行划分。

考虑出度的情况下计算网络分类，具体过程如下：

（1）计算网络中10 个节点的出度，则节点x1～x10的出度依次为4、0、2、0、0、0、1、0、1、0。

Fig.1 Network C图1 网络C

（2）找到出度最大的节点为x1，计算Link(x1)={x2,x4,x5,x8}。

（3）在集合Link(x1)={x2,x4,x5,x8}中计算出{x2,x4,x5,x8}，则第一个分类为CL={x1,x2,x4,x5,x8}，删除节点x1,x2,x4,x5和x8的度，此时节点x1～x10的度依次为0、0、2、0、0、0、1、0、1、0。

（4）计算出此时度最大的节点为x3，Link(x3)={x10}，在Link(x3)中计算，则第二个分类为CL={x3,x10}，删除节点x3和x10的度，此时节点x1～x10的度依次为0、0、0、0、0、0、1、0、1、0。

（5）计算出此时度最大的第一个节点为x7，Link(x7)=∅，则第三个分类为CL={x7}，删除节点x7的度，此时节点x1～x10的度依次为0、0、0、0、0、0、1、0、1、0。

（6）计算出此时度最大的第一个节点为x9，计算Link(x9)=∅，则第四个分类为CL={x9}，删除节点x9的度，此时节点x1～x10的度依次为0、0、0、0、0、0、0、0、0、0。

（7）此时，网络中10 个节点的出度均为0，孤立点x6单独归为一类，即第五个类CL={x6}。综上，得到以下社区划分结果：

即该网络总共分为5 个营销社区。

下面继续对5 个社区的网络特征值进行分析：

Table 2 Network formal context (U,M,A,I) of network in Fig.1表2 图1 的网络对应的网络形式背景(U,M,A,I)

在该社交营销网络中，社区C1和C2的平均度差别不大，说明两个卖家社区在网络当中的重要性差别不大。但C1和C2的平均势差别较大，说明两个社区内部的卖家之间的重要性差别较大，这是因为在社区C1中含有x1，其重要性很大。

在该网络中买家x6、x7和x9没有售卖商品，因此在售卖网络中重要性为0，故它们的网络特征值M1=M2=0。

下面的例2 给出了一个双角色网络的社区划分，以说明算法2 具体如何实施。

例2图2 是一个学术引用网络，网络中节点x1～x20表示20 位作者，字母a～i表示网络中作者经常使用的关键字。从节点x1指向节点x10的箭头表示作者x1引用了作者x10的文章。图2 对应的网络形式背景(U,M,A,I)可由表3 和表4 合并得到，其中表3 为网络中节点之间的连接关系，即作者间的引用关系，表4 为网络中各对象所拥有的属性。

Fig.2 Academic citation network图2 学术引用网络

（1）依据算法2，先考虑基于出度的划分，设β=0.2。从网络中出度最大的节点x2开始划分，可以得到以下分类：

Table 3 Connection relation of network formal context (U,M,A,I) of Fig.2表3 图2 对应的网络形式背景(U,M,A,I)的连接关系

Table 4 Attributes possessed by objects in network formal context (U,M,A,I) of Fig.2表4 图2 对应的网络形式背景(U,M,A,I)所含对象拥有的属性

选取社区C2,C6和C7进行网络特征值的讨论，先分析社区C2：

同理可以得到出度对象形式概念：

引用者社区C6和C7的平均度差别较大，说明它们在网络中的重要性差别较大。而两社区平均势差小，说明两者内部的引用者之间的差异小。

（2）考虑基于入度的划分，设β=0.2。可以得到以下分类：

此处，选取C4进行网络特征值分析：

节点x12的入度为13，而节点x2的入度为14，两者均为度较大的节点。同理，设β=0.2，以节点x12作为起始节点进行分类，可得以下分类结果：

节点x8的入度为11，在整个网络中属于度较大的节点，指向它的节点为：

而这些节点大部分未与节点x8分为一类，主要原因是这些节点虽然与节点x8相连，但并不具有相同的属性。因此，在划分时，不仅要考虑节点的Link值，还要考虑节点所拥有的属性。

（3）考虑基于综合度的划分，设β=0.2，可得以下分类：

这里仅选取C2进行网络特征值分析：

则M1=2.14,M2=0.21。故可得综合度对象形式概念为({2.14,0.21},{x10,x18,x19},{a,j})，其中表示社区C2中的作者共同使用的关键字为a和j，M1=2.14 表示平均度，社区C2中节点重要性为2.14，M2=0.21 表示社区C2中节点之间影响力差异为0.21。

可以发现，在网络社区划分研究中，从不同的角度解决问题，如考虑入度、出度和综合度，得到的社区划分结果是不同的。

4 结束语

本文主要提出了网络结构和属性信息相结合的网络社区划分方法。该方法兼顾了网络的结构特点和网络中节点所拥有的内涵属性。它可以针对不同网络中结构与属性的特点，选取不同的相似阈值对网络进行社区划分以得到社区特征值，从而更好地对网络社区进行认知学习。在本文给出的网络划分算法的基础上，今后可以进一步研究以下问题：（1）基于网络形式背景的网络规则提取；（2）非冗余网络规则的快速提取算法；（3）保持非冗余网络规则不变的知识约简；（4）节点属性特征矩阵为先验信息的网络划分以及关联规则挖掘等。