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

张志颖; 田有亮

doi:10.11959/j.issn.2096-109x.2021098

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-03

- 基于结构熵约束的图聚类方法
- Graph clustering method based on structure entropy constraints
- 网络与信息安全学报 2021年7卷第6期页码：155-166
- 作者机构：
  
  1. 贵州大学计算机科学与技术学院，贵州贵阳 550025
  2. 贵州省公共大数据重点实验室，贵州贵阳 550025
  3. 贵州大学密码学与数据安全研究所，贵州贵阳 550025
- 作者简介：
  
  [ "张志颖（1996− ），男，贵州铜仁人，贵州大学硕士生，主要研究方向为大数据安全与隐私保护、结构信息理论" ]
  [ "田有亮（1982− ），男，贵州盘县人，博士，贵州大学教授、博士生导师，主要研究方向为算法博弈论、密码学与安全协议、大数据安全与隐私保护等" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61662009);国家自然科学基金资助项目;The National Natural Science Foundation of China(61772008);贵州省科技重大专项计划基金;The Major Scientific and Technological Special Project of Guizhou Province,China(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)
- DOI：10.11959/j.issn.2096-109x.2021098
  中图分类号： TP309
- 网络首发：2021-12，
  
  纸质出版：2021-12-15
- 稿件说明：
移动端阅览
张志颖, 田有亮. 基于结构熵约束的图聚类方法[J]. 网络与信息安全学报, 2021,7(6):155-166.

Zhiying ZHANG, Youliang TIAN. Graph clustering method based on structure entropy constraints[J]. Chinese Journal of Network and Information Security, 2021, 7(6): 155-166.
张志颖, 田有亮. 基于结构熵约束的图聚类方法[J]. 网络与信息安全学报, 2021,7(6):155-166. DOI： 10.11959/j.issn.2096-109x.2021098.

Zhiying ZHANG, Youliang TIAN. Graph clustering method based on structure entropy constraints[J]. Chinese Journal of Network and Information Security, 2021, 7(6): 155-166. DOI： 10.11959/j.issn.2096-109x.2021098.

摘要

针对以大数据为中心的信息开放共享平台，如何从嵌入大规模噪声结构的网络中解码出网络的真实结构，进一步在挖掘关联信息的过程中得到较为准确的挖掘结果的问题，提出基于结构熵的聚类方法实现对图中节点关联程度的划分。提出了计算二维结构信息的求解算法和基于熵减原则的模块划分算法，对图结构中节点划分得到对应的模块；利用 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.

关键词

Keywords

references

WU D P , ZHANG Z H , WU S E , et al . Biologically inspired resource allocation for network slices in 5G-enabled internet of things [J ] . IEEE Internet of Things Journal , 2019 , 6 ( 6 ): 9266 - 9279 .

WU S E , GUO H Q , XU J H , et al . In-band full duplex wireless communications and networking for IoT devices:Progress,challenges and opportunities [J ] . Future Generation Computer Systems , 2019 , 92 : 705 - 714 .

BI R W , CHEN Q X , CHEN L , et al . A privacy-preserving personalized service framework through Bayesian game in social IoT [J ] . Wireless Communications and Mobile Computing , 2020 , 2020 : 1 - 13 .

XIE C , XIAO X Y , HASSAN D K . Data mining and application of social e-commerce users based on big data of internet of things [J ] . Journal of Intelligent ＆ Fuzzy Systems , 2020 , 39 ( 4 ): 5171 - 5181 .

MÜLLE Y , CLIFTON C , BÖHM K , . Privacy-integrated graph clustering through differential privacy [C ] // Proceedings of the Workshops of the {EDBT/ICDT} 2015 Joint Conference (EDBT/ICDT) . 2015 : 247 - 254 .

PAUL A , SUPPAKITPAISARN V , BAFNA M , et al . Improving accuracy of differentially private kronecker social networks via graph clustering [C ] // Proceedings of 2020 International Symposium on Networks,Computers and Communications (ISNCC) . 2020 : 1 - 6 .

ZHAN Y , PAN H W , XIE X Q , et al . Graph entropy-based clustering algorithm in medical brain image database [J ] . Journal of Intelligent ＆ Fuzzy Systems , 2016 , 31 ( 2 ): 1029 - 1039 .

LIU Y , NG M K , WU S . Multi-domain networks association for biological data using block signed graph clustering [J ] . IEEE/ACM Transactions on Computational Biology and Bioinformatics , 2020 , 17 ( 2 ): 435 - 448 .

GUO H B , MA Y , TUSKAN G A , et al . A suggestion of converting protein intrinsic disorder to structural entropy using Shannon's information theory [J ] . Entropy , 2019 , 21 ( 6 ): 591 .

KEYVANPOUR M R , MORADI S S . A perturbation method based on singular value decomposition and feature selection for privacy preserving data mining [J ] . International Journal of Data Warehousing and Mining , 2014 , 10 ( 1 ): 55 - 76 .

TEO S G , CAO J , LEE V C . DAG:A general model for privacy-preserving data mining [J ] . IEEE Transactions on Knowledge and Data Engineering , 2018 , 32 ( 1 ): 40 - 53 .

AL-SAGGAF Y , ISLAM M Z . Data mining and privacy of social network sites' users:implications of the data mining problem [J ] . Science and Engineering Ethics , 2015 , 21 ( 4 ): 941 - 966 .

GÖRNERUP O , DOKOOHAKI N , HESS A . Privacy-preserving mining of frequent routes in cellular network data [C ] // Proceedings of 2015 IEEE Trustcom/BigDataSE/ISPA . 2015 : 581 - 587 .

周艺华 , 张冰 , 杨宇光 , 等 . 基于聚类的社交网络隐私保护方法 [J ] . 计算机科学 , 2019 , 46 ( 10 ): 154 - 160 .

ZHOU Y H , ZHANG B , YANG Y G , et al . Cluster-based social network privacy protection method [J ] . Computer Science , 2019 , 46 ( 10 ): 154 - 160 .

YAN S , PAN S R , ZHAO Y H , et al . Towards privacy-preserving data mining in online social networks:distance-grained and item-grained differential privacy [M ] // Information Security and Privacy . Cham : Springer , 2016 : 141 - 157 .

TIAN Y P , YAN J , HU J , et al . A privacy preserving model in uncertain graph mining [C ] // Proceedings of 2018 International Conference on Networking and Network Applications (NaNA) . 2018 : 102 - 106 .

JIANG X L , ZHANG F , ZHANG H . Research on protective mining method for privacy data in network based on apriori algorithm [C ] // Proceedings of 2019 IEEE 14th International Conference on Intelligent Systems and Knowledge Engineering (ISKE) . 2019 : 1241 - 1246 .

REZA K , ISLAM M , ESTIVILL-CASTRO V , . Privacy preservation of social network users against attribute inference attacks via malicious data mining [C ] // Proceedings of the 5th International Conference on Information Systems Security and Privacy . 2019 : 412 - 420 .

ALSHAIKH M , ZOHDY M , OLAWOYIN R , et al . Social network analysis and mining:privacy and security on Twitter [C ] // Proceedings of 2020 10th Annual Computing and Communication Workshop and Conference (CCWC) . 2020 : 712 - 718 .

LI A S , PAN Y C . Structural information and dynamical complexity of networks [J ] . IEEE Transactions on Information Theory , 2016 , 62 ( 6 ): 3290 - 3339 .

LI A S , LI J K , PAN Y C . Discovering natural communities in networks [J ] . Physica A:Statistical Mechanics and Its Applications , 2015 , 436 : 878 - 896 .

LI A S and PAN Y C . Structure entropy and resistor graphs [J ] . CoRR abs,2018,1801.03404 .

LI A S , YIN X C , XU B X , et al . Decoding topologically associating domains with ultralow resolution Hi-C data by graph structural entropy [J ] . Nature Communications , 2018 , 9 ( 1 ): 3265 - 3226 .

LIU Y W , LIU J M , ZHANG Z J , et al . REM:from structural entropy to community structure deception [C ] // Proceedings of 2019 Annual Conference on Neural Information Processing Systems,NeurIPS . 2019 : 12918 - 12928 .

HUFFMAN D A . A method for the construction of minimum-redundancy codes [J ] . Resonance , 2006 , 11 ( 2 ): 91 - 99 .

姜火文 , 曾国荪 , 胡克坤 . 一种遗传算法实现的图聚类匿名隐私保护方法 [J ] . 计算机研究与发展 , 2016 , 53 ( 10 ): 2354 - 2364 .

JIANG H W , ZENG G S , HU K K . An anonymous privacy protection method for graph clustering based on genetic algorithm [J ] . Computer Research and Development , 2016 , 53 ( 10 ): 2354 - 2364 .

CAPÓ M , PÉREZ A , LOZANO J A . An efficient K-means clustering algorithm for tall data [J ] . Data Mining and Knowledge Discovery , 2020 , 34 ( 3 ): 776 - 811 .

LI S S . An improved DBSCAN algorithm based on the neighbor similarity and fast nearest neighbor query [J ] . IEEE Access , 2020 , 8 : 47468 - 47476 .

STOVALL T R , KOCKARA S , AVCI R . GPUSCAN:GPU-based parallel structural clustering algorithm for networks [J ] . IEEE Transactions on Parallel and Distributed Systems , 2015 , 26 ( 12 ): 3381 - 3393 .

浏览量

577

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

具备隐私信息保护能力的学习器研究

面向数据发布和挖掘的隐私保护研究进展