基于节点映射的核型企业重叠社群发现算法

卢志刚 胡昕晨

摘 要：针对现有企业社群发现算法多侧重于同质性市场环境，不能反映部分企业会参与多条供应链作业的问题，提出一种基于节点映射关系的核社群表示模型Map-Community，通过构塑两种角色节点及其相互间不同的映射关系，判断企业的社群归属问题。基于该表示模型提出一种具有近似线性阶时空复杂度的节点映射算法（NMA）。首先，采取过滤操作获得供应链网络拓扑图中的双连通核心图;然后，引入映射度择选出核心企业节点;其次，依据映射判断规则进行局部扩展;最后，通过回溯将局部社群结构拓展至全局网络并发现重叠区域。LFR网络应用实验中，NMA对阈值变化反映出低敏感性，且在实用性方面优于LFM、COPRA和GCE。在企业社交网络进行仿真，利用划分情况总结分布效应意义。实验结果验证了该算法对于企业重叠社群发现的可行性及其在发现质量方面的性能优势。

关键词：节点映射;双连通核心图;核心企业;局部扩展;企业重叠社群发现

中图分类号： TP391

文献标志码：A

文章編号：1001-9081（2019）03-0899-08

Abstract： As most existing enterprise community discovery algorithms focus on homogenous market environment， without reflecting the participation of some enterprises in multiple supply chain operations， a core community representation model based on node mapping relationship， Map-Community， was proposed. By constructing two different role nodes and their different mapping relationships， the ownership community of a enterprise was determined. Based on this representation model， Node Mapping Algorithm （NMA） with approximately-linear time-space complexity was proposed. Firstly， filtering operation was used to obtain the biconnected core graph in the topology diagram of the supply chain network. Secondly， mapping degree was introduced to select the core enterprise nodes. Thirdly， local expansion was performed according to the mapping judgment rules. Finally， the local community structure was extended to the global network by backtracking and overlapping areas were discovered. In the LFR （Lancichinetti-Fortunato-Radicchi） network application experiment， NMA shows low sensitivity to threshold change and is superior to LFM （Local Fitness Maximization）， COPRA （Community Overlap PRopagation Algorithm） and GCE （Greedy Clique Expansion） in terms of practicality. Simulation was carried out in the enterprise social network， and the meaning of distribution effect was summarized by the community division. The experimental results verify the feasibility of this algorithm for overlapping enterprise community discovery and its performance advantages in discovery quality.

Key words： node mapping; biconnected core graph; core enterprise; local expansion; overlapping enterprise community discovery

0 引言

企业社群作为供应链网络拓扑范式的一类模块单元，是基于某些共同属性的节点互连集合。社群内部节点联系相对紧密，而社群外部联系相对稀疏[1-3]。发现供应链网络的企业社群，为探究网络拓扑特性及内在规律提供了中观视角，进而具有重要的研究意义。作为揭示真实供应链网络结构特性的先决条件，企业社群发现问题是现阶段供应链网络研究的重点关注方面。

传统的企业社群发现算法通常唯一化节点归属问题，旨在获得非重叠社群结构。这类算法主要分为三类：第一类是基于启发式的层次聚类方法，包括考虑边介数分裂的GN（Girvan-Newman）算法[4]和基于凝聚效应的CNM（Clauset-Newman-Moore）算法[5]等;第二类是基于目标函数的模块度优化方法，包括极值优化[6-7]和贪心算法[8]等;第三类是引入正规矩阵[9]或者拉普拉斯矩阵[10]的谱聚类方法。此外，还有基于标签传播的LPA（Label Propagation Algorithm）[11-12]和基于信息论的算法[13-14]。这些算法严格圈定了社群边界，对于现实中企业节点多归属现象并不能给出很好的解释。

针对传统的非重叠企业社群研究存在的问题，一些学者将节点多属性特征应用于社群识别过程中，发现了交叉区域。重叠社群发现算法可大致分为三类：第一类是派系过滤方法，CPM（Clique Percolation Method）[15]基于团渗透理论，设置网络建模类型为k团结构，但该算法对完全图依赖性强，并不适用于稀疏网络。第二类是局部优化扩展方法，LWP（Luo-Wang-Promislow）算法[16]利用启发式探索完成局部子图度量优化过程。OSLOM（Order Statistics Local Optimization Method）[17]通过局部聚类统计方法，优化社群挖掘过程。第三类是标签传播方法，COPRA（Community Overlap PRopagation Algorithm）[18]考虑了节点归属的不确定性，改进LPA以实现多标签识别，但参数v的选取难以满足真实网络节点归属社群差异较大的条件。SLPA（Speaker-Listener Label Propagation Algorithm）[19]采用Speaker-Listener传播策略完成历史信息的全读取，但出于对时间复杂度制约因素的考量，该算法并不适用于稠密图。上述方法缺乏对节点类型的差异化处理，并不能完全还原真实供应链网络的社群结构。

针对企业社群的现有研究主要涉及同质类型的问题，近年来以异质性结构为基础的企业环境备受关注。企业社群逐渐成为以一个或几个龙头企业为核心，其他中小型企业作为核心企业的组件供应商，存留于它地理周围的一种链接构体[20]。基于核心节点扩散的思想，LFM（Local Fitness Maximization）算法[21]以随机种子节点作为初始社群，重复利用增删节点引起的适应度变化值判斷新社群组成及交叉区域。GCE（Greedy Clique Expansion）算法[22]探寻极大团子图，并以此作为核心进行贪婪式扩展。上述算法在选核方面存在随机性，而且删除操作还会引发扩展偏差和覆盖不全等问题。

针对现有企业社群方法的不足，需要找到一种相对精准的核型企业重叠社群发现算法，既能够解决节点多归属的现实问题，又能实现网络异质模块的高效划分。本文算法旨在从供应链过滤网络中捕捉核心企业节点，基于企业节点间的映射关系链不断完善社群划分结果。本文的主要工作有：

1）提出一种基于节点映射关系的核社群表示模型Map-Community，用以描述群内企业节点之间的社群归属映射关系。

2）提出节点映射算法（Node Mapping Algorithm，NMA），NMA基于过滤操作可大幅简化企业社群的后续挖掘过程，通过精确定位核心企业可实现高效社群划分工作。算法性能优于COPRA[18]等具有近似线性阶时间复杂度的企业重叠社群发现算法。

2 节点映射核社群发现算法

2.1 节点映射核社群表示模型

对于企业社群的挖掘过程，一些经典的社群发现算法或从网状图的整体结构入手，考虑全局信息[21]，或基于局部节点的作用因素，考虑区域拓展[18，22]。如COPRA算法[18]作为重叠社群发现的代表算法，基于局部性为每个节点存储多标签及其对应的隶属度，但该算法不适用于节点关系混杂的网络。考虑到整体和局部两种切入角度没有完全把握核型企业社群的问题，现引入企业节点间的映射关系，融合两种视角挖掘社群结构。通过不同的映射关系，将同一企业节点关联范围内的成员划分至一个社群。

在此意义上，社群表示模型主要由种子节点、联结节点以及二者的映射关系组成，其中种子节点标识核心企业（Core-Enterprise， CE）角色，联结节点标识配套企业（Supporting-Enterprise， SE）角色，节点映射关系标识种子节点根据映射规则，提取与本节点具有适配主从关系的联结节点过程，具体定义如下。

2.2 节点映射算法

核型企业社群发现的节点映射总体算法由过滤、种子节点选择、扩展和回溯4个阶段构成。通过对原始供应链网络的滤除处理，降低了后续程序的复杂性;然后以选择算法获取的某些种子节点为始端，利用映射规则找到重叠局部社群;最后基于回溯操作扩展至全局网络，完善社群结构。

2.2.1 过滤阶段

本环节需要滤除不参与重叠社群发现的部分非核心企业节点，进而识别出包含重叠社群的供应链网络图中的区域。对于核型企业重叠社群发现的问题，可作如下定义。

2.2.2 种子节点选择阶段

在分离半岛图获得双连通核心图后，需要从中提取种子节点。有如下相关定义。

式（3）是由万有引力定律推理得出，该式结果与节点度数成正比关系，与节点间距离成反比关系。由于网络拓扑特性的存在，用度数反映节点所有信息的做法最为可靠，且能反映与其他节点的交流程度，因此式中候选种子节点u的质量用D（u）表示。节点间的关联度d（u，v）则通过其相异度来体现，而后者与Jaccard相似度SIM（u，v）互补，即d（u，v）=1-SIM（u，v）[23]。当点u和v的相异度值越大（或SIM（u，v）值越小）时，前者对于后者的映射力越小，二者属于同一社群的概率也越小。另外，由式（4）得到的F（u）值越大，说明候选节点u的权威映射越大，它在众邻居节点中的显著性越强，则候选节点u很有可能成为核心节点，即ku=u。

在种子节点选择算法中，先根据两个候选节点间的关联性计算SIM（u，v），再利用函数映射F（u）获得每个企业节点的映射度值。若当前候选种子节点符合映射度值高于其他邻居节点，且同属一个社群的条件，则可输出为种子节点。具体实现过程见算法1。

在双连通核心图中，算法1输出的种子节点集合中的点不一定有最大的度数，但从分布情况上看，它们处于最佳位置。找到合适的种子节点后，下一步将基于映射规则识别邻接社群。

2.2.3 扩展阶段

根据Map-Community模型得，任意节点u的直接映射点来自于其邻居节点集N（u），间接映射点则从点v（v∈N（u））的邻居节点集N（v）中获取，以此类推直至遍历所有具备映射关系的节点。节点映射规则旨在从具有最大映射度值的种子节点切入，度量该点对其他联结节点的映射力。该规则是实现遍历过程的重要条件，同时也是供应链网络社群发现的依据。扩展阶段通过反复迭代，比较节点间的映射强度，进而判断构成映射关系的节点是否同属一个社群，相关定义如下。

在2.2.2节中利用选择算法获知了种子节点集，这一阶段将找出构成社群的其他节点要素。首先，从种子点集Vk中选取函数映射值最大的节点，记为k，此时k可以直接扩展至其邻居节点集N（k）的所有元素;然后对N（k）中每一个节点，与其所有邻接点进行关系影响力的分析，根据map值判断解决映射和社群归属问题;最后把符合映射规则的节点全部写入社群Ck，第一次迭代结束。后续过程初始选择范围应是未划分到任意社群的剩余节点，重复上述步骤。具体实现过程见算法2。

对在过滤阶段得到的双连通核心图中的全部节点多次执行迭代过程，其中初始种子节点扩展适用直接映射判断规则，后续扩展适用间接映射判断规则，直至获知所有可能存在的主从信息，进而整理得核型企业重叠社群构体。

2.2.4 回溯阶段

在双连通核心图中，经过种子节点选择和扩展阶段获得了部分社群划分，接下来需要将半岛图回溯至各个社群划分结构中。对于过滤发生前每个通过桥联结的半岛图，可利用桥中与双连通核心图距离较近的端点将其添加至对应的社群。

2.2.5 映射流程

根据上述各算法阶段的描述，可得如图5所示的节点映射整体算法流程。

2.3 算法复杂度

另外，NMA在計算节点映射关系时，需考虑映射双方的角色及关系信息。在依据邻接存储网络发现社群的过程中，所需节点和边的内存空间分别为O（n）和O（m）。因此NMA的空间复杂度为O（n+m）。

3 实验

为验证基于节点映射的核型企业重叠社群发现算法的有效性，首先将该算法应用于LFR（Lancichinetti-Fortunato-Radicchi）测试网络中，关联LFM、COPRA算法等经典的社群发现算法作结果及性能对比;然后将其应用于企业仿真实验中，获取供应链网络社群划分结果。实验运作环境：处理器 Inter Core i5-7200U CPU@2.50GHz 2.70GHz，内存8GB，操作系统Windows 10，实现语言采用Java。

3.1 LFR网络实验

3.1.1 LFR网络及评价指标

LFR网络是Lancichinetti等[24]提出的用来检验社群发现算法性能的基准测试网络，可通过设置不同的参数值圈定各式网络拓扑形态。其中，n标识网络节点数;表示平均节点度;kmax为网络中的最大节点度;On和Om分别控制网络中重叠节点的数量和归属社群的个数;Cmin和Cmax用于限定社群规模;τ1和τ2分别表示网络节点度和社群容量的幂律分布指数;混合参数μ设定社群内外节点存在链接关系的概率。

由于LFR基准网络的社群组织具有既定结构，因此可将不同算法发现的社群划分结果同此结构进行对比，以测评算法的实用性。过程采用规范互信息（Normalized Mutual Information， NMI）[25-26]作为相似度量指标，定义如下：

算法生成社群与既定结构完全一致;而当NMI（CA，CB）=0时，说明二者完全不一致。

3.1.2 阈值分析

判断NMA中映射关系成立与否的关键在于阈值ε的圈定。 ε值越大，待映射节点归属当前社群的可能性越小，最终划分越容易出现覆盖网络不全的结果。如图6所示，对于3个

不同的τ1值决定的LFR基准网络，评价指标NMI值均保持在0.85以上，这说明阈值ε的取值对NMI指标没有绝对影响，且NMA对ε的敏感性较低。令ε=0.5执行算法得到的社群，一般默认是较为贴合实际的。另外，当τ1=-2时，网络中节点度的差异程度较高，即存在极少数节点引出的链接数量过饱和而多数节点相反的情况，此时通过NMA发现的社群测试值NMI较高，从而论证了NMA对于这样一种节点度分布不均的无标度网络的可适性。

3.1.3 算法比较

首先选取表1所示的接近线性时间复杂度的企业重叠社群发现算法，后续将基于LFR测试网络对各算法进行分析。

表2所列算法应用于不同LFR网络的NMI测试值如图7所示，其中各组子图横纵坐标分别为Om和NMI指标。从全局观察到，NMI值随着Om数量的递增有逐渐降低的趋势，这是由于Om的变化阻滞了社群挖掘进度，进而影响了划分结果的质量。

细分来看，当固定μ值时，NMI指标对n值从2000～10000的变化并不敏感，对应数值基本维持不变。原因在于上述算法皆采用从种子节点出发进行局部探寻的策略，该过程仅与种子所在某区域的子图有关，避开了网络全局性的影响。当固定n值时， μ值从0.1～0.4的变化使得社群内外节点关联水平上升，进而导致社群边界不清晰，因此4种算法的NMI值都出现了不同程度的滑落现象，其中COPRA算法的降幅最为显著，LFM算法次之，GCE算法因其种子团的优势变化并不明显。

如图7（a）（c）所示，当μ取值较小时，NMA和COPRA算法的NMI取值线接近重合;如图7（b）（d）所示，当μ取值较大时，COPRA算法得到的NMI值初期下降程度明显，这是因为μ造成了社群结构模糊，增加了标签选取的难度。随着Om的扩大，NMA和COPRA算法的NMI差距会逐步缩减，此时不易发现重叠社群，前者表现为阈值ε的控制，后者在于非重叠节点标签的选取。

对比NMA和GCE算法，发现前者的划分效果略优于后者，尤其在Om∈[2，5]时，前者的NMI线的位置明显高于后者。GCE算法在程序结束后可能会出现节点归属标签未知的情况，NMA算法基于过滤和回溯过程能够实现网络节点全覆盖，很好地规避了GCE算法存在的风险。

综上，较之LFM、COPRA和GCE算法，NMA在LFR基准网络中的社群发现性能更佳。

3.2 企业社交网络仿真实验

根据供应链运作的特点，可将其内部链节抽象为供应商、制造商、分销商、零售商和消费者5种行为主体。设有覆盖387个节点的6条供应链，其中上述5种主体的数量分别为96，15，46，80，150。该链在特定时间下以交易行为标识的无权无向网络如图8所示。

经过NMA算法的过滤和选择操作后，可识别出核心企业节点为151，153，154，155，156，157。图9以节选原始图为例，完成部分社群挖掘过程。由于所有的联结边均不具备桥的特质，因此无需对节选图进行过滤。

各节点的函数映射值以及算法选择的结果如表3所示，其中“Y”表示节点u被选中为核心企业节点，“N”表示未选中，标记为“Y”的所有节点构成了核心企业节点集合，即Vk={155，156}。

根据图9和表3进行迭代映射过程，第一次迭代结果如图10（a）所示，可得点156的配套企业节点为24，73，74，80，82。第二次迭代结果如图10（b）所示，可得点155的配套企业节点为61，63，66，67，69，74，149（阈值ε=0.5）。

如图11所示，从映射关系规律中可推得社群划分D={C1，C2}，两社群C1和C2的交叉区域即为重叠企业节点74。

继续应用NMA算法拓展至全局供应链网络，可得图12所示的最终社群划分结果。

通过上述仿真实验，最终可得分别以企业151，153，154，155，156，157为核心的6个社群，记作C5，C4，C6，C1，C2，C3，其中社群C1和C2的重叠部分是企业74，C2和C3的重叠区域是企业94。由实验结果可推知以下结论：

1）社群内的节点高联结度表现在，核心企业决定了异构环境的归属社群结构，使得相关配套企业能够在既定范围内专注生产工作，这样一方面削弱了配套企业直面市场的压力，另一方面保证了群内竞合关系的平衡，进而提升企业社群的整体福利享有水平。如制造商156的一级供应商24，73，74，82和二级供应商72，80，91等，受社群C2的圈定影响及企业156的核心映射作用而协作生产相关配件。

2）社群间的低联结度表现于核型社群具有一定的进入壁垒，以维持社群规模的相对稳定，也因此增强了针对外部市场冲击的应变能力。如社群C1由于制造商155的主导作用而具备排他性，因此群外企业22和27等皆为被限制入群。

4 结语

针对企业主从关系提出的节点映射核社群模型，适用于在供应链网络中利用关联邻域信息挖掘核型企业社群的情况。NMA算法在双连通核心图中搜索关键种子节点，利用节点映射规则判断联结节点，最终回归原始供应链网络图获得网络映射社群结构。LFR基准网络和企业仿真网络的实验表明，NMA算法性能较佳，发现的社群质量较好。另外该算法需要对阈值ε在合理控制范围内进行设定，以保证网络社群划分的高覆盖率。后续工作将改进核心企业选择策略，考虑更新时间引发的增量社群发现。

参考文献 （References）

[1] GULBAHCE N， LEHMANN S. The art of community detection [J]. Bioessays， 2008， 30（10）： 934-938.

[2] MUCHA P J， RICHARDSON T， MACON K， et al. Community structure in time dependent，multiscale， and multiplex networks [J]. Science， 2010， 328（5980）： 876-878.

[3] 隆華，李宝安.基于重叠度与模块度增量的复杂网络社区识别[J].计算机应用，2017，37（S1）：6-8.（LONG H， LI B A. Community identificaiton of complex networks based on overlapping degree and module increment [J]. Journal of Computer Applications， 2017， 37（S1）： 6-8.）

[4] NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks [J]. Physical Review E， 2004， 69（2）： 026113.

[5] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826.

GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [EB/OL]. [2018-07-10]. https：//arxiv.org/pdf/cond-mat/0112110.pdf.

[6] DUCH J， ARENAS A. Community detection in complex networks using extremal optimization [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2005， 72（2 Pt 2）： 027104.

[7] BOETTCHER S， PERCUS A G. Optimization with extremal dynamics [J]. Physical Review Letters， 2001， 86（23）： 5211-5214.

[8] NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Physical Review E， 2004， 69（6）： 066133.

[9] CAPOCCI A， SERVEDIO V D P， CALDARELLI G， et al. Detecting communities in large networks [J]. Physica A： Statistical Mechanics and Its Applications， 2005， 352（2/3/4）： 669-676.

[10] DONETTI L， MUOZ M A. Detecting network communities： a new systematic and efficient algorithm [J]. Journal of Statistical Mechanics： Theory and Experiment， 2004， （10）： 10012（只有期）.

DONETTI L， MUOZ M A. Detecting network communities： a new systematic and efficient algorithm [EB/OL]. [2018-07-11]. https：//arxiv.org/pdf/cond-mat/0404652v2.pdf.

[11] RAGHAVAN U N， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2007， 76（3 Pt 2）： 036106.

[12] 陳羽中，施松，朱伟平，等.一种基于邻域跟随关系的增量社区发现算法[J].计算机学报，2017，40（3）： 570-583.（CHEN Y Z， SHI S， ZHU W P， et al. An incremental community discovery algorithm based on neighborhood following relationship [J]. Chinese Journal of Computers， 2017， 40（3）： 570-583.）

[13] ROSVALL M， BERGSTROM C T. Maps of random walks on complex networks reveal community structure [J]. Proceedings of the National Academy of Sciences of the United States of America， 2008， 105（4）： 1118-1123.

[14] 邓小龙，王柏，吴斌，等.基于信息熵的复杂网络社团划分建模和验证[J].计算机研究与发展，2012，49（4）：725-734.（DENG X L， WANG B， WU B， et al. Modularity modeling and evaluation in community detecting of complex network based on information entropy [J]. Journal of Computer Research and Development， 2012， 49（4）： 725-734.）

[15] PALLA G， DERNYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature， 2005， 435（7043）： 814-818.

[16] LUO F， WANG J Z， PROMISLOW E. Exploring local community structures in large networks[C]// WI '06： Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence. Washington， DC： IEEE Computer Society， 2006： 233-239.

[17] LANCICHINETTI A， RADICCHI F， RAMASCO J J， et al. Finding statistically significant communities in networks [J]. PLoS One， 2011， 6（4）： e18961.

[18] GREGORY S. Finding overlapping communities in networks by label propagation [J]. New Journal of Physics， 2010， 12（10）： 103018.

[19] XIE J R， SZYMANSKI B K. Towards linear time overlapping community detection in social networks [C]// Proceedings of the 2012 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 7302. Berlin： Springer， 2012： 25-36.

[20] 項后军，裘斌斌，周宇.核心企业视角下不同集群演化过程的比较研究[J].科学学研究，2015，33（2）：225-233.（XIANG H J， QIU B B， ZHOU Y. The comparative research of the evolution of different industrial clusters with the perspective of ieading firms [J]. Studies in Science of Science， 2015， 33（2）： 225-233.）

[21] LANCICHINETTI A， FORTUNATO S， KERTSZ J. Detecting the overlapping and hierarchical community structure in complex networks [J]. New Journal of Physics， 2009， 11（3）： 033015.

[22] LEE C， REID F， McDAID A， et al. Detecting highly overlapping community structure by greedy clique expansion [EB/OL]. [2014-11-10]. https：//arxiv.org/pdf/1002.1827.pdf.

[23] ANDERSEN R， LANG K J. Communities from seed sets [C]// WWW '06： Proceedings of the 15th International Conference on World Wide Web. New York： ACM， 2006： 223-232.

[24] LANCICHINETTI A， FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2009， 80（1 Pt 2）： 016118.

[25] 陈俊宇，周刚，南煜，等.一种半监督的局部扩展式重叠社区发现方法[J].计算机研究与发展，2016，53（6）：1376-1388.（CHEN J Y， ZHOU G， NAN Y， et al. Semi-supervised local expansion method for overlapping community detection [J]. Journal of Computer Research and Development， 2016， 53（6）： 1376-1388.）

[26] DANON L， DUCH J， DIAZ-GUILERA A， et al. Comparing community structure identification [J]. Journal of Statistical Mechanics： Theory and Experiment， 2005， 2005（9）： P09008.