The increasing importance of Web 2.0 applications during the last years has created significant interest in tools for analyzing and describing collective user activities and emerging phenomena within the Web. Network structures have been widely employed in this context for modeling users, web resources and relations between them. However, the amount of data produced by modern web systems results in networks that are of unprecedented size and complexity, and are thus hard to interpret. To this end, community detection methods attempt to uncover natural groupings of web objects by analyzing the topology of their containing network. There are numerous techniques adopting a global perspective to the community detection problem, i.e. they operate on the complete network structure, thus being computationally expensive and hard to apply in a streaming manner. In order to add a local perspective to the study of the problem, we present Bridge Bounding, a local methodology for community detection, which explores the local network topology around a seed node in order to identify edges that act as boundaries to the local community. The proposed method can be integrated in an efficient global community detection scheme that compares favorably to the state of the art. As a case study, we apply the method to explore the topic structure of the LYCOS iQ collaborative question answering application by detecting communities in the networks created from the collective tagging activity of users.
A combined strategy for community detection is provided by @cite_5 . The authors consider a three-step community detection process: (a) detection of maximal cliques (subgraph enumeration), (b) initial network partition by progressive expansion of the maximal cliques (flooding) and (c) adjustment of the original partition in order to maximize modularity.
@cite_5
2963300816
Community detection is the task of detecting hidden communities from observed interactions. Guaranteed community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and provide guaranteed community detection for a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced by (2008). This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. Moreover, it contains the stochastic block model as a special case. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is fast and is based on simple linear algebraic operations, e.g., singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. As an important special case, our results match the best known scaling requirements for the (homogeneous) stochastic block model.