Community Detection Algorithms Based On Generative Model And Matrix Factorization

Many complex systems in different real-world fields can be represented by complex networks.A key feature of such complex network is the community structure,which is commonly observed that the nodes within a community are densely connected,while nodes in different communities are sparsely connected.Community structure provides useful information for understanding the organization structure of a network and the interaction between different functional modules,as a result,it has been a hot research topic in the study of complex network.In this work,our community detection methods are mainly based on generative model and nonnegative matrix factorization,including the following three parts:(1)Overlapping communities are ubiquitous in complex network,while it is also observed that hubs and outliers exist in networks.Here we proposed a new generative model to detect these three structures simultaneously.Then we formulated our model as nonnegative matrix factorization problem to infer the parameters.We showed that our method can detect the three structures altogether without adjusting extra parameters.Experimental results demonstrate our method can provide more information for analyzing the networks by identifying high quality overlapping communities,hubs and outliers simultaneously.(2)The average sizes of communities are different at different scales,which refers to the hierarchical community structure.Identifying hierarchical and overlapping communities simultaneously reveals more information related to the network.We combined the symmetric nonnegative matrix factorization with l2,1norm regularization term to detect hierarchical and overlapping communities.l2,1norm regularization term can penalize the meaningless communities,so our method can select the meaningful communities automatically.Furthermore,by adjusting the resolution parameter,we can detect the number of communities at different scales,so that we are able to identify hierarchical and overlapping communities altogether.(3)In addition to the network topology,there are available non-topological information on nodes,i.e.,the labels of nodes and the pairwise must-link constraints between nodes.We proposed a semi-supervised learning model to integrate these two information,which guarantees the nodes sharing the same label or having the must-link constraints to be assigned to the same community.Then we proposed an active learning model based on the linear combination of node topologies.This model can select the most representative nodes,and by utilizing the non-topological information on these selected nodes,we can further improve the performance of the semi-supervised learning model.The new methods proposed in this thesis are the effective exploration for community detection and enrich the related research topics.Also,they have both theoretical and practical benefit to further researches on complex network analysis.