基于片段的企业信任网络演化图聚类算法

doi:10.11772/j.issn.1001-9081.2017071726

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 270-276.DOI: 10.11772/j.issn.1001-9081.2017071726

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

基于片段的企业信任网络演化图聚类算法

卢志刚, 解婉婷

上海海事大学经济管理学院, 上海 201306

收稿日期:2017-07-13 修回日期:2017-08-31 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 解婉婷
作者简介:卢志刚(1973-),男,湖北京山人,教授,博士,主要方向:商务智能、供应链优化;解婉婷(1994-),女,江苏镇江人,硕士研究生,主要研究方向:信息管理、电子商务。
基金资助:
上海市基础研究重点项目（15590501800）。

Evolution graph clustering algorithm of enterprise trust network based on fragment

LU Zhigang, XIE Wanting

School of Economics and Management, Shanghai Maritime University, Shanghai 201306, China

Received:2017-07-13 Revised:2017-08-31 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the Basic Research Project of Shanghai (15590501800).

摘要/Abstract

摘要： 针对动态信任网络中企业信任联盟的识别及演变问题，提出一种基于片段的演化图聚类（GC）算法。首先，通过考虑企业信任网络演化的时间信息来对信任网络进行编码；其次，构建划分和表示信任网络结构编码成本的评价函数，如信任联盟稳定则将该时间段内信任网络组成片段压缩表示，如联盟突变则开始新的信任网络片段并重新划分结构；最后，通过搜索最小编码成本，得到信任联盟的稳定结构和结构突变的时间点。仿真实验表明，所提算法能有效识别信任联盟及其结构的突变，且其准确性和运行效率均高于经典社区发现算法。

关键词: 信任网络, 网络演化, 企业分组, 网络片段, 图聚类

Abstract: Concerning the problem about the identification and evolution of enterprise trust alliance in dynamic trust network, a Graph Clustering (GC) algorithm based on fragment was proposed. Firstly, by considering the time information of network evolution, the trust network of enterprise was encoded. Secondly, the evaluation function of coding cost for dividing and presenting the structure of trust network was built. When the trust alliance was stable, the trust network during this time period would be compressed into a fragment; when the alliance changed, a new trust network fragment would be built and the structure of it would be re-devided. Finally, by finding the minimum coding cost, the stable structure of trust alliance and the timestamp of structural mutation could be found. The experimental results indicate that the proposed algorithm can identify the enterprise trust alliances and their mutations; and the accuracy and operating efficiency are higher than the classical community discovery algorithm.

Key words: trust network, network evolution, enterprise grouping, network fragment, Graph Clustering (GC)

中图分类号:

TP391

卢志刚, 解婉婷. 基于片段的企业信任网络演化图聚类算法[J]. 计算机应用, 2018, 38(1): 270-276.

LU Zhigang, XIE Wanting. Evolution graph clustering algorithm of enterprise trust network based on fragment[J]. Journal of Computer Applications, 2018, 38(1): 270-276.

参考文献

[1] 王莉,程学旗.在线社会网络的动态社区发现及演化[J].计算机学报,2015,38(2):219-237.(WANG L, CHENG X Q. Dynamic community in online social networks[J]. Chinese Journal of Computers, 2015, 38(2):219-237.)
[2] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2008(10):155-168.
[3] KARRER B, NEWMAN M E J. Stochastic blockmodels and community structure in networks[J]. Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2010, 83(2):016107.
[4] CAPOCCI A, SERVEDIO V D P, CALDARELLI G, et al. Detecting communities in large networks[J]. Physica A:Statistical Mechanics & Its Applications, 2005, 352(2/3/4):669-676.
[5] LANCICHINETTI A, FORTUNATO S. Community detection algorithms:a comparative analysis[J]. Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2009, 80(5):056117.
[6] CSHEN H, CHENG X, CAI K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A:Statistical Mechanics & Its Applications, 2009, 388(8):1706-1712.
[7] 张学武,沈浩东,赵沛然,等.基于事件框架的社区进化预测研究[J].计算机学报,2017,40(3):729-742.(ZHANG X W, SHEN H D, ZHAO P R, et al. Research on community evolution prediction based on event-based frameworks[J]. Chinese Journal of Computers, 2017, 40(3):729-742.)
[8] BASSETT D S, PORTER M A, WYMBS N F, et al. Robust detection of dynamic community structure in networks[J]. Chaos, 2013, 23(1):013142.
[9] 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.
[10] LIN Y, CHI Y, ZHU S, et al. FacetNet:a framework for analyzing communities and their evolutions in dynamic networks[C]//Proceedings of the 17th International Conference on World Wide Web. New York:ACM, 2008:685-694.
[11] SARKAR P, MOORE A W. Dynamic social network analysis using latent space models[J]. ACM SIGKDD Explorations Newsletter, 2005, 7(2):31-40.
[12] 成全,焦玉英,陆泉,等.基于耗散结构理论的Wiki社区交流动力机制研究[J].图书情报工作,2008,52(11):62-65.(CHENG Q, JIAO Y Y, LU Q, et al. Dynamic mechanisms of communication in Wiki community based on the dissipative structure theory[J]. Library and Information Service, 2008, 52(11):62-65.)
[13] 查日军,张德平,聂长海,等.组合测试数据生成的交叉熵与粒子群算法及比较[J].计算机学报,2010,33(10):1896-1908.(ZHA R J, ZHANG D P, NIE C H, et al. Test data generation algorithms of combinatorial testing and comparison based on cross-entropy and particle swarm optimization method[J]. Chinese Journal of Computers, 2010, 33(10):1896-1908.)
[14] 冯健,丁媛媛.基于重叠社区和结构洞度的社会网络结构洞识别算法[J].计算机工程与科学,2016,38(5):898-904.(FENG J, DING Y Y. A structural hole identification algorithm in social networks based on overlapping communities and structural hole degree[J]. Computer Engineering and Science, 2016, 38(5):898-904.)
[15] WU J, XIONG H, CHEN J. Adapting the right measures for K-means clustering[C]//Proceedings of the 2009 ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York:ACM, 2009:877-886.

基于片段的企业信任网络演化图聚类算法

Evolution graph clustering algorithm of enterprise trust network based on fragment

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

[1]	李杏峰, 黄玉清, 任珍文, 李毅红. 基于自适应邻域的鲁棒多视图聚类算法[J]. 计算机应用, 2021, 41(4): 1093-1099.
[2]	杨丰瑞, 郑云俊, 张昌. 结合概率矩阵分解的混合型推荐算法[J]. 计算机应用, 2018, 38(3): 644-649.
[3]	刘锦文, 邢凯, 芮伟康, 张利萍, 周慧. 基于信息关联拓扑的互联网社交关系挖掘[J]. 计算机应用, 2016, 36(7): 1875-1880.
[4]	肖晓丽, 钱娅丽, 李旦江, 谭柳斌. 基于用户兴趣和社交信任的聚类推荐算法[J]. 计算机应用, 2016, 36(5): 1273-1278.
[5]	张萌, 南志红. 基于用户偏好的信任网络随机游走推荐模型[J]. 计算机应用, 2016, 36(12): 3363-3368.
[6]	康晓东, 王昊, 郭军, 于文勇. 无监督深度学习彩色图像识别方法[J]. 计算机应用, 2015, 35(9): 2636-2639.
[7]	蔡志文, 林建宗. 面向社会化电子商务的信任感知协同过滤推荐方法[J]. 计算机应用, 2015, 35(1): 167-171.
[8]	王晶朱珂汪斌强. 基于用户社会属性及行为特征吸引度的微博粉丝网络演化模型[J]. 计算机应用, 2013, 33(10): 2753-2756.
[9]	丁利向来生刘希玉宋超超. 改进图聚类算法及其应用[J]. 计算机应用, 2012, 32(12): 3278-3282.
[10]	王国辉林果园. 基于图聚类的入侵检测算法研究[J]. 计算机应用, 2011, 31(07): 1898-1900.