Graph clustering method based on structure entropy constraints

Zhiying ZHANG; Youliang TIAN

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

您当前的位置：

首页 >

文章列表页 >

Graph clustering method based on structure entropy constraints

Papers | 更新时间：2024-06-03

- Graph clustering method based on structure entropy constraints
- Chinese Journal of Network and Information Security Vol. 7, Issue 6, Pages: 155-166(2021)
- 作者机构：
  
  1. 贵州大学计算机科学与技术学院，贵州贵阳 550025
  2. 贵州省公共大数据重点实验室，贵州贵阳 550025
  3. 贵州大学密码学与数据安全研究所，贵州贵阳 550025
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2021098
  CLC： TP309
- Online First：2021-12，
  
  Published：15 December 2021
- 稿件说明：
移动端阅览
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：

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 .

Views

577

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on privacy-preserving learning machines

Progress of research on privacy protection for data publication and data mining

Related Author

Yi-zhang JIANG

Shi-tong WANG

Jiao WANG

Ke-feng FAN

Yong WANG

Related Institution

School of Electronic Engineering and Automation, Guilin University of Electronic Technology

China Electronics Standardization Institute

School of Computer Science and Engineering, Guilin University of Electronic Technology

⁰