Validation of community robustness

DOI10.1016/J.CSDA.2017.10.006MaRDI QIDQ1662115zbMATH OpenOpenAlexWikidataFDO

Authors Annamaria Carissimo, Luisa Cutillo, Italia De Feis

Publication date 17 August 2018

Published in Computational Statistics and Data Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.05045

zbMATH Keywords

communitymultiple testingnetworkvariation of information

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Probabilistic graphical models (62H22) Paired and multiple comparisons; multiple testing (62J15)

Abstract: The large amount of work on community detection and its applications leaves unaddressed one important question: the statistical validation of the results. In this paper we present a methodology able to clearly detect if the community structure found by some algorithms is statistically significant or is a result of chance, merely due to edge positions in the network. Given a community detection method and a network of interest, our proposal examines the stability of the partition recovered against random perturbations of the original graph structure. To address this issue, we specify a perturbation strategy and a null model to build a set of procedures based on a special measure of clustering distance, namely Variation of Information, using tools set up for functional data analysis. The procedures determine whether the obtained clustering departs significantly from the null model. This strongly supports the robustness against perturbation of the algorithm used to identify the community structure. We show the results obtained with the proposed technique on simulated and real datasets.

Recommendations

• On community structure validation in real networks
• Computing exact \(p\)-values for community detection
• Robustness of community structure to node removal
• Asymptotic distribution of modularity in networks
• A Hypothesis Testing Framework for Modularity Based Network Community Detection

Cites work

• A classification for community discovery methods in complex networks
• A remark on the existence of finite graphs
• A survey of statistical network models
• A testing based extraction algorithm for identifying significant communities in networks
• Applied functional data analysis. Methods and case studies
• Collective dynamics of `small-world' networks
• Communities in Networks
• Comparing clusterings -- an information based distance
• Fast unfolding of communities in large networks
• Functional data analysis
• Gaussian processes for machine learning.
• scientific article; zbMATH DE number 3514834 (Why is no real title available?)
• scientific article; zbMATH DE number 720689 (Why is no real title available?)
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Statistical analysis of network data. Methods and models
• The asymptotic number of labeled graphs with given degree sequences
• The interval testing procedure: a general framework for inference in functional data analysis
• The Structure and Function of Complex Networks

Cited in

(7)

• Computing exact \(p\)-values for community detection
• Fusing data depth with complex networks: community detection with prior information
• On community structure validation in real networks
• Robustness of community structure to node removal
• Mitigation of attacks and errors on community structure in complex networks
• Clique detection with a given reliability
• Diversification-constrained bipartite network null model with maximum entropy and its numerical solution

Describes a project that uses

Uses Software

• ESSC
• fdatest
• fda (R)
• gprege

This page was built for publication: Validation of community robustness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662115)