Hierarchical community detection method based on enhanced graph and graph neural networks
[Objective]As an effective way to analyze structures and characteristics of a complex network,community detection helps people understand properties and evolution of networks.However,communities in complex networks often contain hierarchical structures,and most existing multi-resolution community detection methods need to search for appropriate resolution parameters to obtain hierarchical community divisions and cannot analyze the association between network topology and node attributes to obtain deep-level community structure information.To address these limitations,we have developed a community detection method that can leverage richer network information while achieving specific accuracy in hierarchical community segmentation.[Methods]In this paper,we propose a hierarchical community detection method(HCEG),based on enhanced graph and Graph Neural Networks(GNN).Specifically,HCEG first utilizes a variational graph autoencoder to reconstruct the network,enabling the link structure of the reconstructed graph to reflect both the topology structure and node information of the original network.Then,by searching for the largest k-plex subgraph in the reconstructed graph,the initial community center is constructed,and features in the attribute network are incorporated into the community generation and graph learning process.Finally,based on the attribute similarity of community members,candidate seed communities are merged and divided into different levels of communities through a GNN model.[Results]Several experiments are conducted to validate the feasibility and effectiveness of the HCEG in hierarchical community detection tasks on multiple attribute networks including user relationship network,scientific publication network,and webpage hyperlink network.Overall experimental results show that the proposed HCEG method can accurately find hierarchical community structures in different types of real networks when compared to other SOTA methods,and HCEG can achieve good community discovery performance in real networks of different sizes.We further investigate the impact of graph enhancement strategies on the community detection performance of the HCEG by varying the proportion of edge augmentation and the type of graph autoencoder.Additionally,we study whether or not graph enhancement strategies should be used.Experimental results on different datasets and levels show that the performance of the HCEG(OG)model(without graph enhancement strategies)is significantly inferior to those of other models,indicating that graph enhancement strategies can effectively improve the performance of the HCEG in community detection tasks.In the process of community expansion,the HCEG method uses an improved GraphSAGE algorithm to match suitable seed communities for the remaining node members in the network.To study the effectiveness of the improved GraphSAGE algorithm in community expansion,we set up a multilayer perceptron(MLP)as a community expansion strategy and compared it with the GraphSAGE.Experimental results show that the HCEG(VGAE+GS)model using the improved GraphSAGE algorithm as a community expansion strategy outperforms the HCEG(VGAE+MLP)model.For the identification of the community categories of nodes in the network,it is not conducive to use only the multilayer perceptron and discard the network topology information.[Conclusions]In this paper,we propose a method for hierarchical community detection based on graph enhancement and graph neural networks,called HCEG.It addresses problems of existing hierarchical community detection methods that cannot efficiently obtain community structures at specific levels and nor can readily leverage attribute network information.By designing a graph enhancement process,the algorithm can integrate the attribute descriptions of node members when we construct initial seed communities,and further merge and expand the obtained initial seed community set to achieve rapid division of communities at various levels.Experimental results on seven real-world datasets show that,compared to other methods,HCEG can fully utilize network information to mine community structures at specific levels in the network.
Hierarchical community detectionGraph neural networksVariational graph auto-encodersAttribute network
万方数据
维普
