Research On Community Detection Algorithms Based On Local Motifs

Complex networks have the characteristics of community structure.Community usually corresponds to different functions and organizational modules of the network.Discovering the community structure within a network is crucial for comprehending the intricate workings and functional development of complex systems.Most of the existing community detection algorithms usually measure the significance of community structure by the connection density between nodes in the community,and can better find communities with high edge density or triangle density in the network community.Nonetheless,as the network grows in size,the links between nodes within the network community become more scattered,rendering the evaluation of community structure significance in terms of connection density inadequate.In fact,nodes in a sparse network often have some special connection modes with high frequency to perform specific community functions.These special connection modes with high frequency are called motif.It is one of the research hotspots of complex network analysis to effectively detect the motifs in the network and apply them to community detection on sparse networks.In this paper,we focus on motif statistics in sparse networks and community detection based on local motif information.The main work is as follows:(1)A network motif analysis platform(NMAP)is built to analyze the motif information in the network from the network level and node level.Firstly,a local motif counting algorithm(LMC)is proposed to count the motif information at the node level in the network,which can calculate the k-motif information of the neighborhood of a specific node in the network,and then calculate the motif information at the network level.The platform can calculate the occurrence frequency,concentration and other absolute motif statistics of different motif in a given network;It can also generate ER random network、WS small-world network、BA scale-free network and LFR artificial network with the same characteristics as the given network,and take these artificially generated networks as the control network to calculate the Z-score,Abundance,Significance Profile(SP)and Subgraph Ration Profile(SRP)of specific motifs in the given network to measure the significance of motifs;The platform can also count the motif information in the neighborhood of a specific node,and analyze the distribution of motifs in the neighborhood of a node.(2)A community detection algorithm with local motif recognition(LMR)is proposed,which combines node-level motif information with node attributes and network topology features to detect community structures with special connection patterns.Firstly,the number of 4-motifs in the neighborhood of the node is calculated by the proposed local motif counting algorithm LMC,and then the normalized network motif matrix is constructed;Then,the graph attention network is used to fuse the motif information,topology information and node attribute characteristics of the network to obtain the node embedding;The algorithm takes the reconstruction loss and clustering loss as the loss function to achieve the goal of optimizing network embedding and community detection results at the same time.(3)A community detection algorithm with local motif similarity(LMS)is proposed,which combines network motif and motif similarity information,topology structure information and node attribute information to detect community structures with special connection patterns.Firstly,the structural similarity of node neighborhood is calculated according to the motif distribution characteristics of node local neighborhood,and then the motif similarity matrix is constructed;The graph attention network is used to fuse the motif information,motif similarity information,topology information and node attribute characteristics of the network to obtain node embedding;Then,the inner product decoder is used to reconstruct the low-order structure and motif similarity information of the graph,and the graph attention decoder is used to reconstruct the node attributes;The algorithm takes the reconstruction loss and clustering loss as the loss function to optimize the network embedding and community detection results at the same time.