网络与信息安全学报 ›› 2021, Vol. 7 ›› Issue (6): 155-166.doi: 10.11959/j.issn.2096-109x.2021098

• 学术论文 • 上一篇    

基于结构熵约束的图聚类方法

张志颖1,2, 田有亮1,2,3   

  1. 1 贵州大学计算机科学与技术学院,贵州 贵阳 550025
    2 贵州省公共大数据重点实验室,贵州 贵阳 550025
    3 贵州大学密码学与数据安全研究所,贵州 贵阳 550025
  • 修回日期:2021-07-01 出版日期:2021-12-01 发布日期:2021-12-01
  • 作者简介:张志颖(1996− ),男,贵州铜仁人,贵州大学硕士生,主要研究方向为大数据安全与隐私保护、结构信息理论
    田有亮(1982− ),男,贵州盘县人,博士,贵州大学教授、博士生导师,主要研究方向为算法博弈论、密码学与安全协议、大数据安全与隐私保护等
  • 基金资助:
    国家自然科学基金(61662009);国家自然科学基金(61772008);贵州省科技重大专项计划(20183001);国家自然科学基金联合基金重点支持项目(U1836205);贵州省科技计划项目([2019]1098);贵州省高层次创新型人才项目([2020]6008)

Graph clustering method based on structure entropy constraints

Zhiying ZHANG1,2, Youliang TIAN1,2,3   

  1. 1 College of Computer Science and Technology, Guizhou University, Guiyang 550025, China
    2 Guizhou Provincial Key Laboratory of Public Big Data, Guiyang 550025, China
    3 Institute of Cryptography &Data Security, Guizhou University, Guiyang 550025, China
  • Revised:2021-07-01 Online:2021-12-01 Published:2021-12-01
  • Supported by:
    TheNational Natural Science Foundation of China(61662009);TheNational Natural Science Foundation of China(61772008);Science and Technology Major Support Program of Guizhou Province(20183001);Key Program of the National Natural Science Union Foundation of China(U1836205);Science and Technology Program of Guizhou Province([2019]1098);Project of High-level Innovative Talents of Guizhou Province([2020]6008)

摘要:

针对以大数据为中心的信息开放共享平台,如何从嵌入大规模噪声结构的网络中解码出网络的真实结构,进一步在挖掘关联信息的过程中得到较为准确的挖掘结果的问题,提出基于结构熵的聚类方法实现对图中节点关联程度的划分。提出了计算二维结构信息的求解算法和基于熵减原则的模块划分算法,对图结构中节点划分得到对应的模块;利用 K 维结构信息算法对已划分的模块做进一步的划分,实现对图结构中节点的聚类;通过实例分析表明,所提出的图聚类方法不仅能够反映图结构的真实结构,而且可以有效地挖掘出图结构中节点之间的关联程度。同时对比了其他3种聚类方法,实验表明该方法在执行时间上具有更高的效率和保证聚类结果的可靠性。

关键词: 数据挖掘, 结构信息, 结构熵, 图聚类

Abstract:

Aiming at the problem of how to decode the true structure of the network from the network embedded in the large-scale noise structure at the open information sharing platform centered on big data, and furthermore accurate mining results can be obtained in the mining related information process, the method of clustering based on structure entropy was proposed to realize divide the correlation degree of nodes in the graph.A solution algorithm for calculating two-dimensional structural information and a module division algorithm based on the principle of entropy reduction were proposed to divide the nodes in the graph structure to obtain corresponding modules.The K-dimensional structural information algorithm was used to further divide the divided modules to realize the clustering of nodes in the graph structure.An example analysis shows that the proposed graph clustering method can not only reflect the true structure of the graph structure, but also effectively mine the degree of association between nodes in the graph structure.At the same time, the other three clustering schemes are compared, and the experiment shows that this scheme has higher efficiency in execution time and guarantees the reliability of the clustering results.

Key words: data mining, structural information, structure entropy, graph clustering

中图分类号: 

No Suggested Reading articles found!