Algorithms Of Identifying Community Structures Based On Matrix Factorization

Community structure is one of the most important features of complex networks and plays an important role in understanding the organizational structures of the network and explaining functions of complex systems.Therefore,a key problem for community detection is how to effectively use the network information to identify community structures fast and accurately.In this thesis,we proposed three community detection methods by using the network generative model and matrix factorization technology.The proposed methods mainly focus on two issues: mining the potentially useful information about the network,and acceleration of iterative algorithms for community detection.Details of our work are as follows:(1)Traditional node community detection algorithms mainly consider weights between nodes,and treat all nodes indiscriminately in the network.These methods also ignore the fact that nodes with higher similarity are more likely in the same community.In view of these problems,we present a novel global and local community detection method by mining the network node weight and local similarity information for better identifying community structures.Thereafter,we derive the multiplicative updating rules to learn parameters of our model.Numerous experiments on both synthetic and real networks demonstrate the effectiveness of the proposed approach.(2)Our above method needs the number of communities and the algorithm is time-consuming in the massive iterative process.In this part,we present a fast node community detection algorithm based on the initialization strategy.Our method uses a larger initial value(or the number of nodes)as the number of communities.Then it utilizes the network Bayesian model to obtain a smaller number of communities during the iterative process.When the algorithm runs to an end,we get the reasonable number of communities.Meanwhile,the algorithm uses two specific factor matrices as the initial strategy to reduce the time spent in the iterative process.(3)Current adjacency matrix mainly considers the weights between immediate neighbour nodes,while it does not take the relationship between non-neighbour nodes into consideration.Meanwhile,the similarity between nodes rather than self-similarity(similarity between node itself)plays a major role in community detection.Thus,in this thesis,we propose a link community detection method by introducing multi-step similarities to fully mine the network information for identifying community structures.The proposed method uses the graph random walk approach to capture the potential reliable link between nodes.Meanwhile,in order to reduce impact caused by selfsimilarities and increase importance gained from similarities between different nodes,we add a penalty term to our objective function for better identifying community structures.The proposed method can be used for detecting both link and node communities.Then,we test the proposed method on both synthetic and real networks.Experimental results demonstrate the effectiveness of the proposed approach.The new methods proposed in this thesis are the effective complements to the current community detection and would provide a reference for the study of related fields.Also,they have both theoretical and practical significance for further complex network analysis.