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

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

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 10

方法	规模	开销	效率	时间复杂度	适合数据
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)$	动态

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

顶点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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 29

Related Articles 3

Metrics

Recommended 0

[1]	Yi-zhang JIANG,Shi-tong WANG. Research on privacy-preserving learning machines [J]. Chinese Journal of Network and Information Security, 2016, 2(6): 22-31.
[2]	Zhi-qiang GAO,Qing-peng LI,Ren-yuan HU. Clustering algorithm preserving differential privacy in the framework of Spark [J]. Chinese Journal of Network and Information Security, 2016, 2(11): 47-51.
[3]	Jiao WANG,Ke-feng FAN,Yong WANG. Progress of research on privacy protection for data publication and data mining [J]. Chinese Journal of Network and Information Security, 2016, 2(1): 18-26.