Community detection, the decomposition of a graph into meaningful building blocks, has been a core research topic in network science over the past years. Since a precise notion of what constitutes a community has remained evasive, community detection algorithms have often been compared on benchmark graphs with a particular form of community structure, and classified based on the mathematical techniques they employ. However, this can be misleading because apparent similarities in their mathematical machinery can disguise entirely different objectives. Here we provide a focused review of the different motivations that underpin community detection. This problem-driven classification is useful in applied network science, where it is important to select an appropriate algorithm for the given purpose. Moreover, highlighting the different facets of community detection also delineates the many lines of research, and points out open directions and avenues for future research.
The many facets of community detection in complex networks
Michael T. Schaub, Jean-Charles Delvenne, Martin Rosvall, Renaud Lambiotte
Ties between individuals on a social network can represent different dimensions of interactions, and the spreading of information and innovations on these networks could potentially be driven by some dimensions more than by others. In this paper we investigate this issue by studying the diffusion of microfinance within rural India villages and accounting for the whole multilayer structure of the underlying social networks. We define a new measure of node centrality, diffusion versatility, and show that this is a better predictor of microfinance participation rate than previously introduced measures defined on aggregated single-layer social networks. Moreover, we untangle the role played by each social dimension and find that the most prominent role is played by the nodes that are central on layers concerned with trust, shedding new light on the key triggers of the diffusion of microfinance.
Untangling the role of diverse social dimensions in the diffusion of microfinance
Elisa Omodei and Alex Arenas
Applied Network Science20161:14
The flocking of animals is often modelled as a dynamical system, in which individuals are represented as particles whose interactions are determined by the current state of the system. Many animals, however, including humans, have predictive capabilities, and presumably base their behavioural decisions—at least partially—upon an anticipated state of their environment. We explore a minimal version of this idea in the context of particles that interact according to a pairwise potential. Anticipation enters the picture by calculating the interparticle forces from linear extrapolation of the positions some time τ into the future. Our analysis shows that for intermediate values of τ the particles rapidly form milling structures, induced by velocity alignment that emerges from the prediction. We also show that for τ>0, any dynamical system governed by an even potential becomes dissipative. These results suggest that anticipation could play an important role in collective behaviour, since it induces pattern formation and stabilises the dynamics of the system.
The impact of anticipation in dynamical systems
P. Gerlee, K. Tunstrøm, T. Lundh, B. Wennberg
Many networks are used to transfer information or goods, in other words, they are navigated. The larger the network, the more difficult it is to navigate efficiently. Indeed, information routing in the Internet faces serious scalability problems due to its rapid growth, recently accelerated by the rise of the Internet of Things. Large networks like the Internet can be navigated efficiently if nodes, or agents, actively forward information based on hidden maps underlying these systems. However, in reality most agents will deny to forward messages, which has a cost, and navigation is impossible. Can we design appropriate incentives that lead to participation and global navigability? Here, we present an evolutionary game where agents share the value generated by successful delivery of information or goods. We show that global navigability can emerge, but its complete breakdown is possible as well. Furthermore, we show that the system tends to self-organize into local clusters of agents who participate in the navigation. This organizational principle can be exploited to favor the emergence of global navigability in the system.
Collective navigation of complex networks: Participatory greedy routing
Kaj-Kolja Kleineberg, Dirk Helbing
September 25-29, 2017, Puebla, Mexico
The aim of LANET is to provide with a forum to join all scientists who are somehow related to the research on Network Science in Latin America.
The rapid growth of the field of Network Science in the last two decades has manifested in the form of schools, workshops and conferences in Latin America. However, the creation of LANET as a stable and periodic forum devoted to Network Science will further spur the formation of research groups interested in the field and help to establish it as a discipline across Latin American Universities and Research Institutions.