计算机应用 ›› 2019, Vol. 39 ›› Issue (3): 899-906.DOI: 10.11772/j.issn.1001-9081.2018071628

• 应用前沿、交叉与综合 • 上一篇    下一篇

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

卢志刚, 胡昕晨   

  1. 上海海事大学 经济管理学院, 上海 201306
  • 收稿日期:2018-08-06 修回日期:2018-09-02 出版日期:2019-03-10 发布日期:2019-03-11
  • 通讯作者: 胡昕晨
  • 作者简介:卢志刚(1973-),男,湖北荆门人,教授,博士,主要研究方向:大数据分析、商务智能、供应链管理;胡昕晨(1994-),女,山东滕州人,硕士研究生,主要研究方向:大数据分析、商务智能。
  • 基金资助:

    上海市自然科学基金资助项目(18ZR1416900)。

Discovery algorithm for overlapping enterprise community with kernel based on node mapping

LU Zhigang, HU Xinchen   

  1. College of Economics and Management, Shanghai Maritime University, Shanghai 201306, China
  • Received:2018-08-06 Revised:2018-09-02 Online:2019-03-10 Published:2019-03-11
  • Supported by:

    This work is partially supported by the Natural Science Foundation of Shanghai (18ZR1416900).

摘要:

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

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

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

中图分类号: