Search

Many community detection algorithms are stochastic in nature, and their output can vary based on different input parameters and random seeds. Consensus clustering methods, such as FastConsensus and ECG, combine clusterings from multiple runs of the same clustering algorithm, in order to improve stability and accuracy. In this study we present a new consensus clustering method, FastEnsemble, and show that it provides advantages over both FastConsensus and ECG. Furthermore, FastEnsemble is designed for use with any clustering method, and we show results using \ourmethod with Leiden optimizing modularity or the Constant Potts model. FastEnsemble is available in Github at https://github.com/ytabatabaee/fast-ensemble, Comment: 12 pages, 5 figures, submitted to a conference

Since true communities within real-world networks are rarely known, synthetic networks with planted ground truths are valuable for evaluating the performance of community detection methods. Of the synthetic network generation tools available, Stochastic Block Models (SBMs) produce networks with ground truth clusters that well approximate input parameters from real-world networks and clusterings. However, we show that SBMs can produce disconnected ground truth clusters, even when given parameters from clusterings where all clusters are connected. Here we describe the REalistic Cluster Connectivity Simulator (RECCS), a technique that modifies an SBM synthetic network to improve the fit to a given clustered real-world network with respect to edge connectivity within clusters, while maintaining the good fit with respect to other network and cluster statistics. Using real-world networks up to 13.9 million nodes in size, we show that RECCS, applied to stochastic block models, results in synthetic networks that have a better fit to cluster edge connectivity than unmodified SBMs, while providing roughly the same quality fit for other network and clustering parameters as unmodified SBMs., Comment: 12 pages, 5 figures

Community detection approaches resolve complex networks into smaller groups (communities) that are expected to be relatively edge-dense and well-connected. The stochastic block model (SBM) is one of several approaches used to uncover community structure in graphs. In this study, we demonstrate that SBM software applied to various real-world and synthetic networks produces poorly-connected to disconnected clusters. We present simple modifications to improve the connectivity of SBM clusters, and show that the modifications improve accuracy using simulated networks.

In 2002, Kleinberg proposed three axioms for distance-based clustering, and proved that it was impossible for a clustering method to satisfy all three. While there has been much subsequent work examining and modifying these axioms for distance-based clustering, little work has been done to explore axioms relevant to the graph partitioning problem when the graph is unweighted and given without a distance matrix. Here, we propose and explore axioms for graph partitioning for this case, including modifications of Kleinberg's axioms and three others: two axioms relevant to the ``Resolution Limit'' and one addressing well-connectedness. We prove that clustering under the Constant Potts Model satisfies all the axioms, while Modularity clustering and iterative k-core both fail many axioms we pose. These theoretical properties of the clustering methods are relevant both for theoretical investigation as well as to practitioners considering which methods to use for their domain science studies.

In 2006, Warnow, Evans, Ringe, and Nakhleh proposed a stochastic model (hereafter, the WERN 2006 model) of multi-state linguistic character evolution that allowed for homoplasy and borrowing. They proved that if there is no borrowing between languages and homoplastic states are known in advance, then the phylogenetic tree of a set of languages is statistically identifiable under this model, and they presented statistically consistent methods for estimating these phylogenetic trees. However, they left open the question of whether a phylogenetic network -- which would explicitly model borrowing between languages that are in contact -- can be estimated under the model of character evolution. Here, we establish that under some mild additional constraints on the WERN 2006 model, the phylogenetic network topology is statistically identifiable, and we present algorithms to infer the phylogenetic network. We discuss the ramifications for linguistic phylogenetic network estimation in practice, and suggest directions for future research., Comment: 16 pages, 2 figures

Integral to the problem of detecting communities through graph clustering is the expectation that they are "well connected". In this respect, we examine five different community detection approaches optimizing different criteria: the Leiden algorithm optimizing the Constant Potts Model, the Leiden algorithm optimizing modularity, Iterative K-Core Clustering (IKC), Infomap, and Markov Clustering (MCL). Surprisingly, all these methods produce, to varying extents, communities that fail even a mild requirement for well connectedness. To remediate clusters that are not well connected, we have developed the "Connectivity Modifier" (CM), which, at the cost of coverage, iteratively removes small edge cuts and re-clusters until all communities produced are well connected. Results from real-world and synthetic networks illustrate a tradeoff users make between well connected clusters and coverage, and raise questions about the "clusterability" of networks and models of community structure.

Through discovery of meso-scale structures, community detection methods contribute to the understanding of complex networks. Many community finding methods, however, rely on disjoint clustering techniques, in which node membership is restricted to one community or cluster. This strict requirement limits the ability to inclusively describe communities since some nodes may reasonably be assigned to many communities. We have previously reported Iterative K-core Clustering (IKC), a scalable and modular pipeline that discovers disjoint research communities from the scientific literature. We now present Assembling Overlapping Clusters (AOC), a complementary meta-method for overlapping communities as an option that addresses the disjoint clustering problem. We present findings from the use of AOC on a network of over 13 million nodes that captures recent research in the very rapidly growing field of extracellular vesicles in biology., Comment: This version submitted to Quantitative Science Studies

Clustering and community detection in networks are of broad interest and have been the subject of extensive research that spans several fields. We are interested in the relatively narrow question of detecting communities of scientific publications that are linked by citations. These publication communities can be used to identify scientists with shared interests who form communities of researchers. Building on the well-known k-core algorithm, we have developed a modular pipeline to find publication communities. We compare our approach to communities discovered by the widely used Leiden algorithm for community finding. Using a quantitative and qualitative approach, we evaluate community finding results on a citation network consisting of over 14 million publications relevant to the field of extracellular vesicles.

Understanding the nature and organization of scientific communities is of broad interest. The `Invisible College' is a historical metaphor for one such type of community and the search for such `colleges' can be framed as the detection and analysis of small groups of scientists working on problems of common interests. Case studies have previously been conducted on individual communities with respect to their scientific and social behavior. In this study, we introduce, a new and scalable community finding approach. Supplemented by expert assessment, we use the convergence of two different clustering methods to select article clusters generated from over two million articles from the field of immunology spanning an eleven year period with relevant cluster quality indicators for evaluation. Finally, we identify author communities defined by these clusters. A sample of the article clusters produced by this pipeline was reviewed by experts, and shows strong thematic relatedness, suggesting that the inferred author communities may represent valid communities of practice. These findings suggest that such convergent approaches may be useful in the future.

Co-citation measurements can reveal the extent to which a concept representing a novel combination of existing ideas evolves towards a specialty. The strength of co-citation is represented by its frequency, which accumulates over time. Of interest is whether underlying features associated with the strength of co-citation can be identified. We use the proximal citation network for a given pair of articles (x, y) to compute theta, an a priori estimate of the probability of co-citation between x and y, prior to their first co-citation.Thus, low values for theta reflect pairs of articles for which co-citation is presumed less likely. We observe that co-citation frequencies are a composite of power-law and lognormal distributions, and that very high co-citation frequencies are more likely to be composed of pairs with low values of theta, reflecting the impact of a novel combination of ideas. Furthermore, we note that the occurrence of a direct citation between two members of a co-cited pair increases with co-citation frequency. Finally, we identify cases of frequently co-cited publications that accumulate co-citations after an extended period of dormancy.

Species tree estimation from multi-locus datasets is statistically challenging for multiple reasons, including gene tree heterogeneity across the genome due to incomplete lineage sorting (ILS). Species tree estimation methods have been developed that operate by estimating gene trees and then using those gene trees to estimate the species tree. Several of these methods (e.g., ASTRAL, ASTRID, and NJst) are provably statistically consistent under the multi-species coalescent (MSC) model, provided that the gene trees are estimated correctly, and there is no missing data. Recently, Nute et al. (BMC Genomics 2018) addressed the question of whether these methods remain statistically consistent under random models of taxon deletion, and asserted that they do so. Here we provide a counterexample to one of these theorems, and establish that ASTRID and NJst are not statistically consistent under an i.i.d. model of taxon deletion., Comment: 6 pages, no figures, provides counterexample to theorem (the first and corresponding author are both co-authors on this paper)

Computer science has experienced dramatic growth and diversification over the last twenty years. Towards a current understanding of the structure of this discipline, we analyze a cohort of the computer science literature using the DBLP database. For insight on the features of this cohort and the relationship within its components, we constructed article level clusters based on either direct citations or co-citations, and reconciled them to major and minor subject categories in the Scopus All Science Journal Classification (ASJC). We described complementary insights from clustering by direct citation and co-citation, and both point to the increase in computer science publications and their scope. Our analysis shows cross-category clusters, some that interact with external fields, such as the biological sciences, while others remain inward looking.

Citation analysis of the scientific literature has been used to study and define disciplinary boundaries, to trace the dissemination of knowledge, and to estimate impact. Co-citation, the frequency with which pairs of publications are cited, provides insight into how documents relate to each other and across fields. Co-citation analysis has been used to characterize combinations of prior work as conventional or innovative and to derive features of highly cited publications. Given the organization of science into disciplines, a key question is the sensitivity of such analyses to frame of reference. Our study examines this question using semantically-themed citation networks. We observe that trends reported to be true across the scientific literature do not hold for focused citation networks, and we conclude that inferring novelty using co-citation analysis and random graph models benefits from disciplinary context.

Species tree estimation is a complex problem, due to the fact that different parts of the genome can have different evolutionary histories than the genome itself. One of the causes for this discord is incomplete lineage sorting (also called deep coalescence), which is a population-level process that produces gene trees that differ from the species tree. The last decade has seen a large number of new methods developed to estimate species trees from multi-locus datasets, specifically addressing this cause of gene tree heterogeneity. In this paper, we review these methods, focusing mainly on issues that relate to analyses of datasets containing large numbers of species or loci (or both). We also discuss divide-and-conquer strategies for enabling species tree estimation methods to run on large datasets, including new approaches that are based on algorithms (such as TreeMerge) for the Disjoint Tree Merger problem., Comment: 25 pages, no figures, submitted as a chapter for a book edited by Lacey Knowles and Laura Kubatko

Supertree construction is the process by which a set of phylogenetic trees, each on a subset of the overall set X of species, is combined into a tree on the full set S. The traditional use of supertree methods is the assembly of a large species tree from previously computed smaller species trees; however, supertree methods are also used to address large-scale tree estimation using divide-and-conquer (i.e., a dataset is divided into overlapping subsets, trees are constructed on the subsets, and then combined using the supertree method). Because most supertree methods are heuristics for NP-hard optimization problems, the use of supertree estimation on large datasets is challenging, both in terms of scalability and accuracy. In this paper, we describe the current state of the art in supertree construction and the use of supertree methods in divide-and-conquer strategies. Finally, we identify directions where future research could lead to improved supertree methods., Comment: 28 pages, will be part of Festschrift volume for Bernard More

With advances in sequencing technologies, there are now massive amounts of genomic data from across all life, leading to the possibility that a robust Tree of Life can be constructed. However, "gene tree heterogeneity", which is when different genomic regions can evolve differently, is a common phenomenon in multi-locus datasets, and reduces the accuracy of standard methods for species tree estimation that do not take this heterogeneity into account. New methods have been developed for species tree estimation that specifically address gene tree heterogeneity, and that have been proven to converge to the true species tree when the number of loci and number of sites per locus both increase (i.e., the methods are said to be "statistically consistent"). Yet, little is known about the biologically realistic condition where the number of sites per locus is bounded. We show that when the sequence length of each locus is bounded (by any arbitrarily chosen value), the most common approaches to species tree estimation that take heterogeneity into account (i.e., traditional fully partitioned concatenated maximum likelihood and newer approaches, called summary methods, that estimate the species tree by combining gene trees) are not statistically consistent, even when the heterogeneity is extremely constrained. The main challenge is the presence of conditions such as long branch attraction that create biased tree estimation when the number of sites is restricted. Hence, our study uncovers a fundamental challenge to species tree estimation using both traditional and new methods., Comment: Submitted

Many biological questions, including the estimation of deep evolutionary histories and the detection of remote homology between protein sequences, rely upon multiple sequence alignments (MSAs) and phylogenetic trees of large datasets. However, accurate large-scale multiple sequence alignment is very difficult, especially when the dataset contains fragmentary sequences. We present UPP, an MSA method that uses a new machine learning technique - the Ensemble of Hidden Markov Models - that we propose here. UPP produces highly accurate alignments for both nucleotide and amino acid sequences, even on ultra-large datasets or datasets containing fragmentary sequences. UPP is available at https://github.com/smirarab/sepp., Comment: Online supplemental materials and data are available at http://www.cs.utexas.edu/users/phylo/software/upp/

Because biological processes can make different loci have different evolutionary histories, species tree estimation requires multiple loci from across the genome. While many processes can result in discord between gene trees and species trees, incomplete lineage sorting (ILS), modeled by the multi-species coalescent, is considered to be a dominant cause for gene tree heterogeneity. Coalescent-based methods have been developed to estimate species trees, many of which operate by combining estimated gene trees, and so are called summary methods. Because summary methods are generally fast, they have become very popular techniques for estimating species trees from multiple loci. However, recent studies have established that summary methods can have reduced accuracy in the presence of gene tree estimation error, and also that many biological datasets have substantial gene tree estimation error, so that summary methods may not be highly accurate on biologically realistic conditions. Mirarab et al. (Science 2014) presented the statistical binning technique to improve gene tree estimation in multi-locus analyses, and showed that it improved the accuracy of MP-EST, one of the most popular coalescent-based summary methods. Statistical binning, which uses a simple statistical test for combinability and then uses the larger sets of genes to re-calculate gene trees, has good empirical performance, but using statistical binning within a phylogenomics pipeline does not have the desirable property of being statistically consistent. We show that weighting the recalculated gene trees by the bin sizes makes statistical binning statistically consistent under the multispecies coalescent, and maintains the good empirical performance. Thus, "weighted statistical binning" enables highly accurate genome-scale species tree estimation, and is also statistical consistent under the multi-species coalescent model., Comment: (1) In Press, PLoS ONE