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

Evolution graph clustering algorithm of enterprise trust network based on fragment

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

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.