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. This may present serious issues in subsequent analyses. 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. Based on our results, we conclude that the Leiden algorithm is preferable to the Louvain algorithm.
From Louvain to Leiden: guaranteeing well-connected communities
Vincent Traag, Ludo Waltman, Nees Jan van Eck
Applied Big History: A Guide for Entrepreneurs, Investors, and Other Living Things (9781719853071): William Grassie: Amazon Books
Foreword by Mitch Julis, Canyon Partners
- Thriving in a Complex World
- The Great Matrix
- The Economy of a Single Cell
- Complexity Economics
- Death and Taxes
- Your Hunter-Gatherer Brain
- The Big Lollapaloozas
- Existential Challenges
- The Bottom Line
In recent years, parallel developments in disparate disciplines have focused on what has come to be termed connectivity; a concept used in understanding and describing complex systems. Conceptualisations and operationalisations of connectivity have evolved largely within their disciplinary boundaries, yet similarities in this concept and its application among disciplines are evident. However, any implementation of the concept of connectivity carries with it both ontological and epistemological constraints, which leads us to ask if there is one type or set of approach(es) to connectivity that might be applied to all disciplines. In this review we explore four ontological and epistemological challenges in using connectivity to understand complex systems from the standpoint of widely different disciplines. These are: (i) defining the fundamental unit for the study of connectivity; (ii) separating structural connectivity from functional connectivity; (iii) understanding emergent behaviour; and (iv) measuring connectivity. We draw upon discipline-specific insights from Computational Neuroscience, Ecology, Geomorphology, Neuroscience, Social Network Science and Systems Biology to explore the use of connectivity among these disciplines. We evaluate how a connectivity-based approach has generated new understanding of structural-functional relationships that characterise complex systems and propose a ‘common toolbox’ underpinned by network-based approaches that can advance connectivity studies by overcoming existing constraints.
Connectivity and complex systems: learning from a multi-disciplinary perspective
Laura Turnbull, Marc-Thorsten Hütt, Andreas A. Ioannides, Stuart Kininmonth, Ronald Poeppl, Klement Tockner, Louise J. Bracken, Saskia Keesstra, Lichan Liu, Rens Masselink and Anthony J. Parsons
Applied Network Science 2018 3:11
It is widely agreed that the standard genetic code must have been preceded by a simpler code that encoded fewer amino acids. How this simpler code could have expanded into the standard genetic code is not well understood because most changes to the code are costly. Taking inspiration from the recently synthesized six-letter code, we propose a novel hypothesis: the initial genetic code consisted of only two letters, G and C, and then expanded the number of available codons via the introduction of an additional pair of letters, A and U. Various lines of evidence, including the relative prebiotic abundance of the earliest assigned amino acids, the balance of their hydrophobicity, and the higher GC content in genome coding regions, indicate that the original two nucleotides were indeed G and C. This process of code expansion probably started with the third base, continued with the second base, and ended up as the standard genetic code when the second pair of letters was introduced into the first base. The proposed process is consistent with the available empirical evidence, and it uniquely avoids the problem of costly code changes by positing instead that the code expanded its capacity via the creation of new codons with extra letters.
The Standard Genetic Code can Evolve from a Two-Letter GC Code Without Information Loss or Costly Reassignments
Alejandro Frank, Tom Froese
Origins of Life and Evolution of Biospheres
June 2018, Volume 48, Issue 2, pp 259–272