Dataset Information

From Louvain to Leiden: guaranteeing well-connected communities.

ABSTRACT: Community detection is often used to understand the structure of large and complex networks. One of the most popular algorithms for uncovering community structure is the so-called Louvain algorithm. We show that this algorithm has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively. In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected. To address this problem, we introduce the Leiden algorithm. We prove that the Leiden algorithm yields communities that are guaranteed to be connected. In addition, we prove that, when the Leiden algorithm is applied iteratively, it converges to a partition in which all subsets of all communities are locally optimally assigned. Furthermore, by relying on a fast local move approach, the Leiden algorithm runs faster than the Louvain algorithm. We demonstrate the performance of the Leiden algorithm for several benchmark and real-world networks. We find that the Leiden algorithm is faster than the Louvain algorithm and uncovers better partitions, in addition to providing explicit guarantees.

SUBMITTER: Traag VA

PROVIDER: S-EPMC6435756 | biostudies-literature | 2019 Mar

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

From Louvain to Leiden: guaranteeing well-connected communities.

Traag V A VA Waltman L L van Eck N J NJ

Scientific reports 20190326 1

Community detection is often used to understand the structure of large and complex networks. One of the most popular algorithms for uncovering community structure is the so-called Louvain algorithm. We show that this algorithm has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively. In our experimental analysis, we o ...[more]

PMID: 30914743

Similar Datasets

Project description:Due to the ubiquity of mobile phones around the globe, studies are beginning to analyze their influence on health. Prior work from developed countries highlights negative mental health outcomes related to overuse of mobile phones. However, there is little work on mental health impacts of mobile phone use or ownership in developing countries. This is an important gap to address because there are likely variations in mental health impacts of mobile phones between developing and developed countries, due to cultural nuances to phone use and distinct variations in financial models for obtaining mobile phone access in developing countries. To address this gap, this study analyzes survey data from 92 households in sparse, rural villages in Uganda to test two hypotheses about mobile phone ownership and mental health in a developing country context: (i) Mobile phone ownership is higher among more privileged groups, compared to less privileged groups (ie, wealth and ethnicity); and (ii) mobile phone ownership is positively associated with a culturally-relevant indicator of mental health, 'feelings of peace'. Results indicate that households with mobile phones had higher levels of wealth on average, yet no significant differences were detected by ethnicity. As hypothesized, mobile phone ownership was associated with increased mental well-being for persons without family nearby (in the District) (p = 0.038) after adjusting for wealth, ethnicity and amount of land for crops and land for grazing. Mobile phone ownership was not significantly associated with increased mental well-being for persons with family nearby. These findings are consistent with studies of mobile phone use in other sub-Saharan African countries which find that phones are important tools for social connection and are thus beneficial for maintaining family ties. One might infer then that this increased feeling of mental well-being for persons located farther from family stems from the ability to maintain family connections. These findings are quite different from work in developed countries where mobile phone use is a source of technology-related stress or technostress.

Project description:Population viability of a single species, when evaluated with metapopulation based landscape evaluation tools, always increases when the connectivity of the landscape increases. However, when interactions between species are taken into account, results can differ. We explore this issue using a stochastic spatially explicit meta-community model with 21 competing species in five different competitive settings: (1) weak, coexisting competition, (2) neutral competition, (3) strong, excluding competition, (4) hierarchical competition and (5) random species competition. The species compete in randomly generated landscapes with various fragmentation levels. With this model we study species loss over time. Simulation results show that overall diversity, the species richness in the entire landscape, decreases slowly in fragmented landscapes whereas in well-connected landscapes rapid species losses occur. These results are robust with respect to changing competitive settings, species parameters and spatial configurations. They indicate that optimal landscape configuration for species conservation differs between metapopulation approaches, modelling species separately and meta-community approaches allowing species interactions. The mechanism behind this is that species in well-connected landscapes rapidly outcompete each other. Species that become abundant, by chance or by their completive strength, send out large amounts of dispersers that colonize and take over other patches that are occupied by species that are less abundant. This mechanism causes rapid species loss. In fragmented landscapes the colonization rate is lower, and it is difficult for a new species to establish in an already occupied patch. So, here dominant species cannot easily take over patches occupied by other species and higher diversity is maintained for a longer time. These results suggest that fragmented landscapes have benefits for species conservation previously unrecognized by the landscape ecology and policy community. When species interactions are important, landscapes with a low fragmentation level can be better for species conservation than well-connected landscapes. Moreover, our results indicate that metapopulation based landscape evaluation tools may overestimate the value of connectivity and should be replaced by more realistic meta-community based tools.

Project description:Protected areas (PAs) are the main instrument for biodiversity conservation, which has triggered the development of numerous indicators and assessments on their coverage, performance and efficiency. The connectivity of the PA networks at a global scale has however been much less explored; previous studies have either focused on particular regions of the world or have only considered some types of PAs. Here we present, and globally assess, ProtConn, an indicator of PA connectivity that (i) quantifies the percentage of a study region covered by protected connected lands, (ii) can be partitioned in several components depicting different categories of land (unprotected, protected or transboundary) through which movement between protected locations may occur, (iii) is easy to communicate, to compare with PA coverage and to use in the assessment of global targets for PA systems. We apply ProtConn to evaluate the connectivity of the PA networks in all terrestrial ecoregions of the world as of June 2016, considering a range of median dispersal distances (1-100 km) encompassing the dispersal abilities of the large majority of terrestrial vertebrates. We found that 9.3% of the world is covered by protected connected lands (average for all the world's ecoregions) for a reference dispersal distance of 10 km, increasing up to 11.7% for the largest dispersal distance considered of 100 km. These percentages are considerably smaller than the global PA coverage of 14.7%, indicating that the spatial arrangement of PAs is only partially successful in ensuring connectivity of protected lands. The connectivity of PAs largely differed across ecoregions. Only about a third of the world's ecoregions currently meet the Aichi Target of having 17% of the terrestrial realm covered by well-connected systems of PAs. Finally, our findings suggest that PAs with less strict management objectives (allowing the sustainable use of resources) may play a fundamental role in upholding the connectivity of the PA systems. Our analyses and indicator make it possible to identify where on the globe additional efforts are most needed in expanding or reinforcing the connectivity of PA systems, and can be also used to assess whether newly designated sites provide effective connectivity gains in the PA system by acting as corridors or stepping stones between other PAs. The results of the ProtConn indicator are available, together with a suite of other global PA indicators, in the Digital Observatory for Protected Areas of the Joint Research Centre of the European Commission.

Dataset Information

From Louvain to Leiden: guaranteeing well-connected communities.

Publications

From Louvain to Leiden: guaranteeing well-connected communities.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets