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

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

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

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

张志颖¹^,², 田有亮¹^,²^,³

¹ 贵州大学计算机科学与技术学院，贵州贵阳 550025
² 贵州省公共大数据重点实验室，贵州贵阳 550025
³ 贵州大学密码学与数据安全研究所，贵州贵阳 550025

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

Graph clustering method based on structure entropy constraints

Zhiying ZHANG¹^,², Youliang TIAN¹^,²^,³

¹ College of Computer Science and Technology, Guizhou University, Guiyang 550025, China
² Guizhou Provincial Key Laboratory of Public Big Data, Guiyang 550025, China
³ Institute of Cryptography ＆Data Security, Guizhou University, Guiyang 550025, China

Revised:2021-07-01 Online:2021-12-15 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)

摘要/Abstract

摘要：

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

中图分类号:

TP309

张志颖, 田有亮. 基于结构熵约束的图聚类方法[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.

图/表 10

图1

图2

图3

图4

图5

表1

表2

聚类功能对比Table 2 clustering function comparison"

方法	规模	开销	效率	时间复杂度	适合数据
K-means ^[27]	小	大	低	$O (n k t)$	静态
DBSCAN ^[28]	适中	适中	适中	$O (n [\frac{1}{SeedsNum} \log_{n} + {MinPts}^{2}])$	静态
GPUSCAN ^[29]	大	大	高	$O (n^{2})$	静态
本文方法	大	小	高	$O (n \cdot m)$	动态

表2

图6

图7

图8

参考文献 29

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	周艺华, 张冰, 杨宇光 ,等. 基于聚类的社交网络隐私保护方法[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.
[15]	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.
[16]	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.
[17]	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.
[18]	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.
[19]	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.
[20]	LI A S , PAN Y C . Structural information and dynamical complexity of networks[J]. IEEE Transactions on Information Theory, 2016,62(6): 3290-3339.
[21]	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.
[22]	LI A S and PAN Y C . Structure entropy and resistor graphs[J]. CoRR abs,2018,1801.03404.
[23]	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.
[24]	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.
[25]	HUFFMAN D A . A method for the construction of minimum-redundancy codes[J]. Resonance, 2006,11(2): 91-99.
[26]	姜火文, 曾国荪, 胡克坤 . 一种遗传算法实现的图聚类匿名隐私保护方法[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.
[27]	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.
[28]	LI S S . An improved DBSCAN algorithm based on the neighbor similarity and fast nearest neighbor query[J]. IEEE Access, 2020,8: 47468-47476.
[29]	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.

顶点n	边m	二维结构信息划分结果	K维结构信息聚类结果
10	21	X₁:(3,4,8)	X₁:(8,(3,4))
		X₂:(0,5,6,9)	X₂:((0,5),(6,9))
		X₃:(1,2,7)	X₃:(7,(1,2))
20	80	X₁:(0,1,8,11)	X₁:((0,11),(1,8))
		X₂:(4,5,6,15)	X₂:((4,5),(6,15))
		X₃:(2,10,14,16,19)	X₃:((10,19),(2,(14,16)))
		X₄:(3,7,13,17,18)	X₄:((3,(13,17)),(7,18))
		X₅:(9,12)	X₅:(9,12)
30	274	X₁:(2,4,6,8,9,10,20,23,24,25)	X₁:(((6,24),(9,23)),((2,8),(10,25)),(4,20))
		X₂:(0,3,5,11,12,14,19,21,26,27,28,29)	X₂:(((10,11),(5,21)),((29,(12,26)),(3,28)),
		X₃:(1,7,13,15,16,17,18,22)	(14,(19,27)))
			X₃:(((1,(16,18)),(15,22)),(13,(7,17)))
40	442	X₁:(0,1,2,3,5,11,14,16,18,20,	X₁:(((34,(3,20)),(36,(11,37))),((18,(1,2)),
		21,22,29,34,36,37,39)	(39,(16,29))),((5,22),(14,(0,21))))
		X₂:(4,6,7,9,10,12,13,17,23,	X₂:(((6,(13,32)),(33,35)),((17,(10,25)),
		24,25,27,32,33,35,38)	(4,23)),((24,27),(7,12),(9,38)))
		X₃:(8,15,19,26,28,30,31)	X₃:((15,(19,32)),((8,28),(26,30)))

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

Graph clustering method based on structure entropy constraints

在线阅读

pdf下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 29

相关文章 3

Metrics

推荐阅读 0

[1]	蒋惯樟,王士同. 具备隐私信息保护能力的学习器研究[J]. 网络与信息安全学报, 2016, 2(6): 22-31.
[2]	高志强,李庆鹏,胡人远. 基于Spark的支持隐私保护的聚类算法[J]. 网络与信息安全学报, 2016, 2(11): 47-51.
[3]	王姣,范科峰,王勇. 面向数据发布和挖掘的隐私保护研究进展[J]. 网络与信息安全学报, 2016, 2(1): 18-26.