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: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.

Project description:IntroductionWell-care use can positively impact adolescents' current and future health. Understanding adolescents' longitudinal well-care use is critical to determine to whom and when to target engagement strategies to improve healthcare access. This study describes prospective well-care use patterns from childhood through adolescence stratified by sex.MethodsThe sample (N=6,872) was drawn from the Child/Young Adult component of the household-based 1979 National Longitudinal Survey of Youth consisting of biological children born to female respondents (1980-1997). Well-care use (routine checkup with a doctor within last year) data were assessed from age 5 years (1986-2003) until age 17 years (1998-2015). Conducted in 2019, latent class analyses stratified by sex identified well-care use patterns reported over 7 biennial time points adjusted for cohort, race/ethnicity, urbanicity, maternal education, and insurance.ResultsA total of 4 well-care use classes emerged for female adolescents: the majority belonged to Engaged (37%) and Moderately Engaged (39%) classes and the remainder belonged to Gradually Re-engaged (14%) and Disengaged-with-Rebound (10%) classes. A total of 3 classes emerged for male adolescents: the majority belonged to the Persistently Disengaged (48%) class and the remainder belonged to Engaged (34%) and Gradually Re-engaged (18%) classes. For both sexes, comparing each cohort with the first, Engaged class membership increased for subsequent cohorts. Less engaged well-care use classes had more non-Hispanic White adolescents living in rural areas with lower insurance coverage. Maternal education differentiated well-care use classes for male but not for female adolescents, being higher for male adolescents in the Engaged class than in other classes.ConclusionsThese findings highlight that well-care use patterns for both sexes changed during the transition from childhood to adolescence and that class membership differed by covariates. These results suggest that sex-specific strategies may be needed to enhance adolescents' well-care use engagement over time.

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.

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