Browse
Submit Data
Databases
API
Help

Dataset Information

18 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Community Detection on Networks with Ricci Flow.

ABSTRACT: Many complex networks in the real world have community structures - groups of well-connected nodes with important functional roles. It has been well recognized that the identification of communities bears numerous practical applications. While existing approaches mainly apply statistical or graph theoretical/combinatorial methods for community detection, in this paper, we present a novel geometric approach which enables us to borrow powerful classical geometric methods and properties. By considering networks as geometric objects and communities in a network as a geometric decomposition, we apply curvature and discrete Ricci flow, which have been used to decompose smooth manifolds with astonishing successes in mathematics, to break down communities in networks. We tested our method on networks with ground-truth community structures, and experimentally confirmed the effectiveness of this geometric approach.

SUBMITTER: Ni CC

PROVIDER: S-EPMC6620345 | biostudies-literature | 2019 Jul

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Community Detection on Networks with Ricci Flow.

Ni Chien-Chun CC Lin Yu-Yao YY Luo Feng F Gao Jie J

Scientific reports 20190710 1

Many complex networks in the real world have community structures - groups of well-connected nodes with important functional roles. It has been well recognized that the identification of communities bears numerous practical applications. While existing approaches mainly apply statistical or graph theoretical/combinatorial methods for community detection, in this paper, we present a novel geometric approach which enables us to borrow powerful classical geometric methods and properties. By consid ...[more]

PMID: 31292482

Similar Datasets

Ollivier-Ricci Curvature-Based Method to Community Detection in Complex Networks.

Project description:Identification of community structures in complex network is of crucial importance for understanding the system's function, organization, robustness and security. Here, we present a novel Ollivier-Ricci curvature (ORC) inspired approach to community identification in complex networks. We demonstrate that the intrinsic geometric underpinning of the ORC offers a natural approach to discover inherent community structures within a network based on interaction among entities. We develop an ORC-based community identification algorithm based on the idea of sequential removal of negatively curved edges symptomatic of high interactions (e.g., traffic, attraction). To illustrate and compare the performance with other community identification methods, we examine the ORC-based algorithm with stochastic block model artificial networks and real-world examples ranging from social to drug-drug interaction networks. The ORC-based algorithm is able to identify communities with either better or comparable performance accuracy and to discover finer hierarchical structures of the network. This opens new geometric avenues for analysis of complex networks dynamics.

| S-EPMC6611887 | biostudies-literature

Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature.

Project description:Describing networks geometrically through low-dimensional latent metric spaces has helped design efficient learning algorithms, unveil network symmetries and study dynamical network processes. However, latent space embeddings are limited to specific classes of networks because incompatible metric spaces generally result in information loss. Here, we study arbitrary networks geometrically by defining a dynamic edge curvature measuring the similarity between pairs of dynamical network processes seeded at nearby nodes. We show that the evolution of the curvature distribution exhibits gaps at characteristic timescales indicating bottleneck-edges that limit information spreading. Importantly, curvature gaps are robust to large fluctuations in node degrees, encoding communities until the phase transition of detectability, where spectral and node-clustering methods fail. Using this insight, we derive geometric modularity to find multiscale communities based on deviations from constant network curvature in generative and real-world networks, significantly outperforming most previous methods. Our work suggests using network geometry for studying and controlling the structure of and information spreading on networks.

| S-EPMC8316456 | biostudies-literature

Measuring robustness of brain networks in autism spectrum disorder with Ricci curvature.

Project description:Ollivier-Ricci curvature is a method for measuring the robustness of connections in a network. In this work, we use curvature to measure changes in robustness of brain networks in children with autism spectrum disorder (ASD). In an open label clinical trials, participants with ASD were administered a single infusion of autologous umbilical cord blood and, as part of their clinical outcome measures, were imaged with diffusion MRI before and after the infusion. By using Ricci curvature to measure changes in robustness, we quantified both local and global changes in the brain networks and their potential relationship with the infusion. Our results find changes in the curvature of the connections between regions associated with ASD that were not detected via traditional brain network analysis.

| S-EPMC7331646 | biostudies-literature

Intrinsic 3D Dynamic Surface Tracking based on Dynamic Ricci Flow and Teichmuller Map.

Project description:3D dynamic surface tracking is an important research problem and plays a vital role in many computer vision and medical imaging applications. However, it is still challenging to efficiently register surface sequences which has large deformations and strong noise. In this paper, we propose a novel automatic method for non-rigid 3D dynamic surface tracking with surface Ricci flow and Teichmüller map methods. According to quasi-conformal Teichmüller theory, the Techmüller map minimizes the maximal dilation so that our method is able to automatically register surfaces with large deformations. Besides, the adoption of Delaunay triangulation and quadrilateral meshes makes our method applicable to low quality meshes. In our work, the 3D dynamic surfaces are acquired by a high speed 3D scanner. We first identified sparse surface features using machine learning methods in the texture space. Then we assign landmark features with different curvature settings and the Riemannian metric of the surface is computed by the dynamic Ricci flow method, such that all the curvatures are concentrated on the feature points and the surface is flat everywhere else. The registration among frames is computed by the Teichmüller mappings, which aligns the feature points with least angle distortions. We apply our new method to multiple sequences of 3D facial surfaces with large expression deformations and compare them with two other state-of-the-art tracking methods. The effectiveness of our method is demonstrated by the clearly improved accuracy and efficiency.

| S-EPMC5844492 | biostudies-literature

Robust detection of dynamic community structure in networks.

Project description:We describe techniques for the robust detection of community structure in some classes of time-dependent networks. Specifically, we consider the use of statistical null models for facilitating the principled identification of structural modules in semi-decomposable systems. Null models play an important role both in the optimization of quality functions such as modularity and in the subsequent assessment of the statistical validity of identified community structure. We examine the sensitivity of such methods to model parameters and show how comparisons to null models can help identify system scales. By considering a large number of optimizations, we quantify the variance of network diagnostics over optimizations ("optimization variance") and over randomizations of network structure ("randomization variance"). Because the modularity quality function typically has a large number of nearly degenerate local optima for networks constructed using real data, we develop a method to construct representative partitions that uses a null model to correct for statistical noise in sets of partitions. To illustrate our results, we employ ensembles of time-dependent networks extracted from both nonlinear oscillators and empirical neuroscience data.

| S-EPMC3618100 | biostudies-other

Improved community detection in weighted bipartite networks.

Project description:Real-world complex networks are composed of non-random quantitative interactions. Identifying communities of nodes that tend to interact more with each other than the network as a whole is a key research focus across multiple disciplines, yet many community detection algorithms only use information about the presence or absence of interactions between nodes. Weighted modularity is a potential method for evaluating the quality of community partitions in quantitative networks. In this framework, the optimal community partition of a network can be found by searching for the partition that maximizes modularity. Attempting to find the partition that maximizes modularity is a computationally hard problem requiring the use of algorithms. QuanBiMo is an algorithm that has been proposed to maximize weighted modularity in bipartite networks. This paper introduces two new algorithms, LPAwb+ and DIRTLPAwb+, for maximizing weighted modularity in bipartite networks. LPAwb+ and DIRTLPAwb+ robustly identify partitions with high modularity scores. DIRTLPAwb+ consistently matched or outperformed QuanBiMo, while the speed of LPAwb+ makes it an attractive choice for detecting the modularity of larger networks. Searching for modules using weighted data (rather than binary data) provides a different and potentially insightful method for evaluating network partitions.

| S-EPMC4736915 | biostudies-literature

Multi-resolution community detection in massive networks.

Project description:Aiming at improving the efficiency and accuracy of community detection in complex networks, we proposed a new algorithm, which is based on the idea that communities could be detected from subnetworks by comparing the internal and external cohesion of each subnetwork. In our method, similar nodes are firstly gathered into meta-communities, which are then decided to be retained or merged through a multilevel label propagation process, until all of them meet our community criterion. Our algorithm requires neither any priori information of communities nor optimization of any objective function. Experimental results on both synthetic and real-world networks show that, our algorithm performs quite well and runs extremely fast, compared with several other popular algorithms. By tuning a resolution parameter, we can also observe communities at different scales, so this could reveal the hierarchical structure of the network. To further explore the effectiveness of our method, we applied it to the E-Coli transcriptional regulatory network, and found that all the identified modules have strong structural and functional coherence.

| S-EPMC5154182 | biostudies-literature

Community-Based Event Detection in Temporal Networks.

Project description:We propose a method for detecting large events based on the structure of temporal communication networks. Our method is motivated by findings that viral information spreading has distinct diffusion patterns with respect to community structure. Namely, we hypothesize that global events trigger viral information cascades that easily cross community boundaries and can thus be detected by monitoring intra- and inter-community communications. By comparing the amount of communication within and across communities, we show that it is possible to detect events, even when they do not trigger a significantly larger communication volume. We demonstrate the effectiveness of our method using two examples-the email communication network of Enron and the Twitter communication network during the Boston Marathon bombing.

| S-EPMC6416296 | biostudies-literature

Community detection in networks without observing edges.

Project description:We develop a Bayesian hierarchical model to identify communities of time series. Fitting the model provides an end-to-end community detection algorithm that does not extract information as a sequence of point estimates but propagates uncertainties from the raw data to the community labels. Our approach naturally supports multiscale community detection and the selection of an optimal scale using model comparison. We study the properties of the algorithm using synthetic data and apply it to daily returns of constituents of the S&P100 index and climate data from U.S. cities.

| S-EPMC6981088 | biostudies-literature

Comparative analysis of two discretizations of Ricci curvature for complex networks.

Project description:We have performed an empirical comparison of two distinct notions of discrete Ricci curvature for graphs or networks, namely, the Forman-Ricci curvature and Ollivier-Ricci curvature. Importantly, these two discretizations of the Ricci curvature were developed based on different properties of the classical smooth notion, and thus, the two notions shed light on different aspects of network structure and behavior. Nevertheless, our extensive computational analysis in a wide range of both model and real-world networks shows that the two discretizations of Ricci curvature are highly correlated in many networks. Moreover, we show that if one considers the augmented Forman-Ricci curvature which also accounts for the two-dimensional simplicial complexes arising in graphs, the observed correlation between the two discretizations is even higher, especially, in real networks. Besides the potential theoretical implications of these observations, the close relationship between the two discretizations has practical implications whereby Forman-Ricci curvature can be employed in place of Ollivier-Ricci curvature for faster computation in larger real-world networks whenever coarse analysis suffices.

| S-EPMC5988801 | biostudies-other

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data