The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative deﬁnition of community is not implemented in the algorithms, leading to an intrinsic difﬁculty in the interpretation of the results without any additional non-topological information. In this article we deal with this problem by showing how quantitative deﬁnitions of community are implemented in practice in the existing algorithms. In this way the algorithms for the identiﬁcation of the community structure become fully self-contained. Furthermore, we propose a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artiﬁcial and real-world graphs. In particular, we show how the algorithm applies to a network of scientiﬁc collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems.
Giorgio BertiniResearch on society, culture, art, neuroscience, cognition, critical thinking, intelligence, creativity, autopoiesis, self-organization, rhizomes, complexity, systems, networks, leadership, sustainability, thinkers, futures ++
4000 Posts in this Blog
- Follow Learning Change on WordPress.com