Characterization of complex networks: A survey of measurements

Abstract

Each complex network (or class of networks) presents specific topological features which characterize its connectivity and highly influence the dynamics of processes executed on the network. The analysis, discrimination, and synthesis of complex networks therefore rely on the use of measurements capable of expressing the most relevant topological features. This article presents a survey of such measurements. It includes general considerations about complex network characterization, a brief review of the principal models, and the presentation of the main existing measurements. Important related issues covered in this work comprise the representation of the evolution of complex networks in terms of trajectories in several measurement spaces, the analysis of the correlations between some of the most traditional measurements, perturbation analysis, as well as the use of multivariate statistics for feature selection and network classification. Depending on the network and the analysis task one has in mind, a specific set of features may be chosen. It is hoped that the present survey will help the proper application and interpretation of measurements.

A working manuscript with 78 pages, 32 figures. Suggestions of measurements for inclusion are welcomed by the authors

References in corpus (52)

• Modularity and community structure in networks
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Functional cartography of complex metabolic networks
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Community detection in complex networks using Extremal Optimization
• Self-similarity of complex networks
• Subgraph Centrality in Complex Networks
• Detecting rich-club ordering in complex networks
• Finding local community structure in networks
• Modeling Cascading Failures in the North American Power Grid
• k-core organization of complex networks
• The Rich-Club Phenomenon In The Internet Topology
• The spatial structure of networks
• Characterization and Modeling of weighted networks
• On the uniform generation of random graphs with prescribed degree sequences
• A Local Method for Detecting Communities
• Spectral Measures of Bipartivity in Complex Networks
• Cycles and clustering in bipartite networks
• Networks and Cities: An Information Perspective
• Spatial Growth of Real-world Networks
• Entropy Optimization of Scale-Free Networks Robustness to Random Failures
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• On network bipartivity
• When are networks truly modular?
• An Information-Theoretic Approach to Network Modularity
• Hierarchical characterization of complex networks
• Searchability of Networks
• Edge vulnerability in neural and metabolic networks
• Hide and seek on complex networks
• Vulnerability and Hierarchy of Complex Networks
• Cyclic Topology in Complex Networks
• Offdiagonal Complexity: A computationally quick complexity measure for graphs and networks
• Information Horizons in Networks
• Extremal Properties of Random Structures
• Equilibrium statistical mechanics of network structures
• The shortest path to complex networks
• Email as Spectroscopy: Automated Discovery of Community Structure within Organizations
• Systematic identification of statistically significant network measures
• Effect of degree correlations on the loop structure of scale-free networks
• Assortative mixing by degree makes a network more unstable
• Organization of complex networks without multiple connections
• Effect of size heterogeneity on community identification in complex networks
• Morphological complex networks: Can individual morphology determine the general connectivity and dynamics of networks?
• Clustering coefficient without degree correlations biases
• Synchronization of degree correlated physical networks
• The Dynamics of Hierarchical Evolution of Complex Networks
• Hub-Based Community Finding
• Networks and Our Limited Information Horizon
• Beyond the average: detecting global singular nodes from local features in complex networks
• A Review of Recent Studies of Geographical Scale-Free Networks

Cited by in corpus (318)

• Epidemic processes in complex networks
• Synchronization in complex networks
• The structure and dynamics of multilayer networks
• Link Prediction in Complex Networks: A Survey
• Temporal Networks
• Predicting Missing Links via Local Information
• How to project a bipartite network?
• The Kuramoto model in complex networks
• Recommender Systems
• Statistical physics of vaccination
• Adaptive Coevolutionary Networks: A Review
• Missing and spurious interactions and the reconstruction of complex networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Communicability in complex networks
• Evolutionary games on multilayer networks: A colloquium
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Complex network approaches to nonlinear time series analysis
• Recurrence networks - A novel paradigm for nonlinear time series analysis
• Recurrence-based time series analysis by means of complex network methods
• The physics of brain network structure, function, and control
• Graph analysis of functional brain networks: practical issues in translational neuroscience
• A Tutorial in Connectome Analysis: Topological and Spatial Features of Brain Networks
• Generative models of the human connectome
• Modelling the Air Transport with Complex Networks: a short review
• Core-periphery organization of complex networks
• Spreading processes in Multilayer Networks
• Information dynamics shape the networks of Internet-mediated prostitution
• Fundamentals of spreading processes in single and multilayer complex networks
• A Multi-Scale Analysis of 27,000 Urban Street Networks: Every US City, Town, Urbanized Area, and Zillow Neighborhood
• Combining complex networks and data mining: why and how
• Tag-Aware Recommender Systems: A State-of-the-art Survey
• The Geometry of Chaotic Dynamics -- A Complex Network Perspective
• Communicability Betweenness in Complex Networks
• Optimal hierarchical modular topologies for producing limited sustained activation of neural networks
• Urban street networks: a comparative analysis of ten European cities
• Link Prediction with Node Clustering Coefficient
• Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks
• Scale-free networks without growth
• Analytical framework for recurrence-network analysis of time series
• Network reconstruction from random phase-resetting
• Empirical analysis of web-based user-object bipartite networks
• Deciphering Network Community Structure by Surprise
• Strong correlations between text quality and complex networks features
• A simple rule for axon outgrowth and synaptic competition generates realistic connection lengths and filling fractions
• Resolving structural variability in network models and the brain
• Disease Localization in Multilayer Networks
• Correlation between centrality metrics and their application to the opinion model
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Disentangling different types of El Niño episodes by evolving climate network analysis
• Graph measures and network robustness
• Surprise maximization reveals the community structure of complex networks
• Structural Evolution of the Brazilian Airport Network
• Hypergraph model of social tagging networks
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• What Would a Graph Look Like in This Layout? A Machine Learning Approach to Large Graph Visualization
• A complex network approach to stylometry
• Evaluating Network Models: A Likelihood Analysis
• Quantifying loopy network architectures
• Neural development features: Spatio-temporal development of the Caenorhabditis elegans neuronal network
• Random matrix analysis of complex networks
• Climate Dynamics: A Network-Based Approach for the Analysis of Global Precipitation
• Rich-club connectivity dominates assortativity and transitivity of complex networks
• From brain to earth and climate systems: Small-world interaction networks or not?
• Removing spurious interactions in complex networks
• Knowledge Acquisition: A Complex Networks Approach
• A dynamic model of time-dependent complex networks
• Density-based and transport-based core-periphery structures in networks
• Exact solution of mean geodesic distance for Vicsek fractals
• Structural constraints in complex networks
• Node-weighted measures for complex networks with spatially embedded, sampled, or differently sized nodes
• A review on turbulent and vortical flow analyses via complex networks
• Classifying informative and imaginative prose using complex networks
• Machine Learning in Network Centrality Measures: Tutorial and Outlook
• Symmetry based Structure Entropy of Complex Networks
• Structure-semantics interplay in complex networks and its effects on the predictability of similarity in texts
• Visibility graph analysis of wall turbulence time-series
• Exact analytical solution of average path length for Apollonian networks
• Random Graph Modeling: A survey of the concepts
• Emergent multistability and frustration in phase-repulsive networks of oscillators
• Quantifying the interdisciplinarity of scientific journals and fields
• Structure and Interpretation of Computer Programs
• Uncovering missing links with cold ends
• Synchronization in symmetric bipolar population networks
• Adaptive financial networks with static and dynamic thresholds
• Analyzing complex networks through correlations in centrality measurements
• A complex network approach to robustness and vulnerability of spatially organized water distribution networks
• Mapping and discrimination of networks in the complexity-entropy plane
• The Potential of the Human Connectome as a Biomarker of Brain Disease
• Time Series Analysis via Network Science: Concepts and Algorithms
• Authorship Attribution Based on Life-Like Network Automata
• The Web of Connections between Tourism Companies in Elba: Structure and Dynamics
• SimiNet: a Novel Method for Quantifying Brain Network Similarity
• Estimating the impact of structural directionality: How reliable are undirected connectomes?
• Paragraph-based complex networks: application to document classification and authenticity verification
• Variations of the Hydrogen Bonding and of the Hydrogen Bonded Network in Ethanol-Water Mixtures on Cooling
• Network science: a review focused on tourism
• An Analysis of Centrality Measures for Complex and Social Networks
• Border Detection in Complex Networks
• Three-feature model to reproduce the topology of citation networks and the effects from authors' visibility on their h-index
• Comparing intermittency and network measurements of words and their dependency on authorship
• Linguistic data mining with complex networks: a stylometric-oriented approach
• Fractal scale-free networks resistant to disease spread
• Critical paths in a metapopulation model of H1N1: Efficiently delaying influenza spreading through flight cancellation
• On time-varying collaboration networks
• Topological-collaborative approach for disambiguating authors' names in collaborative networks
• Corporate competition: A self-organized network
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Ising model on the Apollonian network with node dependent interactions
• Characterisation of spatial network-like patterns from junctions' geometry
• Predicting epidemic outbreak from individual features of the spreaders
• Revealing biases in the sampling of ecological interaction networks
• Broad lifetime distributions for ordering dynamics in complex networks
• Localization properties of a tight-binding electronic model on the Apollonian network
• Random matrix analysis of network Laplacians
• Optimization in Networks
• Multiplex visibility graphs to investigate recurrent neural networks dynamics
• A Review of Features for the Discrimination of Twitter Users: Application to the Prediction of Offline Influence
• Predicting missing links via significant paths
• Talking by the numbers: Networks identify productive forum discussions
• Spreading dynamics on spatially constrained complex brain networks
• Surrogate-assisted analysis of weighted functional brain networks
• Topologies and Laplacian spectra of a deterministic uniform recursive tree
• How much random a random network is : a random matrix analysis
• Enhancing automated reaction discovery with boxed molecular dynamics in energy space
• Higher order assortativity in complex networks
• q-state Potts model on the Apollonian network
• Multifractal characterisation of particulate matter (PM10) time series in the Caribbean basin using visibility graphs
• Statistical validation of high-dimensional models of growing networks
• Motif analysis in directed ordered networks and applications to food webs
• Multifractal Characterization of Protein Contact Networks
• Disentangling synchrony from serial dependency in paired event time series
• Rumor propagation with heterogeneous transmission in social networks
• Beyond the average: Detecting global singular nodes from local features in complex networks
• Integrating temporal and spatial scales: Human structural network motifs across age and region-of-interest size
• Empirical study on clique-degree distribution of networks
• A new measure for community structures through indirect social connections
• Spatial characterization of turbulent channel flow via complex networks
• Accessibility Measure for Eternal Inflation: Dynamical Criticality and Higgs Metastability
• Recursive weighted treelike networks
• Antiferromagnetic Ising model in small-world networks
• Chain motifs: The tails and handles of complex networks
• Concentric Characterization and Classification of Complex Network Nodes: Theory and Application to Institutional Collaboration
• An Evolving model of online bipartite networks
• Transition from fractal to non-fractal scalings in growing scale-free networks
• Developmental time windows for axon growth influence neuronal network topology
• What are the Best Hierarchical Descriptors for Complex Networks?
• A generative model for protein contact networks
• Cooperation in the Prisoner's Dilemma game in Random Scale-Free Graphs
• The effects of degree correlations on network topologies and robustness
• Improving local clustering based top-L link prediction methods via asymmetrical link clustering information
• A geometric growth model interpolating between regular and small-world networks
• Revising the simple measures of assortativity in complex networks
• Analytical results for stochastically growing networks: connection to the zero range process
• Characteristics of Real Futures Trading Networks
• Studying complex tourism systems: a novel approach based on networks derived from a time series
• Modeling and verifying a broad array of network properties
• Musical Genres: Beating to the Rhythms of Different Drums
• Spectral Perturbation and Reconstructability of Complex Networks
• Insights On Streamflow Predictability Across Scales Using Horizontal Visibility Graph Based Networks
• Cycle and flow trusses in directed networks
• Conedy: a scientific tool to investigate Complex Network Dynamics
• Lower bound of assortativity coefficient in scale-free networks
• Authorship attribution via network motifs identification
• From regular to growing small-world networks
• Characterization of graphs for protein structure modeling and recognition of solubility
• Reconstructing dynamical networks via feature ranking
• Internet Topology over Time
• A comparative analysis of knowledge acquisition performance in complex networks
• Emergence of scale-free close-knit friendship structure in online social networks
• Generative Model Selection Using a Scalable and Size-Independent Complex Network Classifier
• Extracting Hidden Hierarchies in 3D Distribution Networks
• Functional structure in production networks
• Characterization of Subgraphs Relationships and Distribution in Complex Networks
• Automatic Network Fingerprinting through Single-Node Motifs
• Analysis of heat kernel highlights the strongly modular and heat-preserving structure of proteins
• Using Complex Networks to Quantify Consistency in the Use of Words
• Geometric and dynamic perspectives on phase-coherent and noncoherent chaos
• The scaling of the minimum sum of edge lengths in uniformly random trees
• A note on measurement of network vulnerability under random and intentional attacks
• Dissociable changes in functional network topology underlie early category learning and development of automaticity
• Phase-Space Networks of Geometrical Frustrated Systems
• Antiferromagnetic Ising model in scale-free networks
• Labelled network subgraphs reveal stylistic subtleties in written texts
• Multifractality in random networks with power-law decaying bond strengths
• Structural and spectral properties of a family of deterministic recursive trees: Rigorous solutions
• A Similarity Approach to Cities and Features
• Scale-variant topological information for characterizing the structure of complex networks
• Link-space formalism for network analysis
• Molecular aggregation in liquid water: Laplace spectra and spectral clustering of H-bonded network
• Hierarchical Spatial Organization of Geographical Networks
• Self-avoiding walks and connective constants in clustered scale-free networks
• Scale-Free Networks with the Same Degree Distribution: Different Structural Properties
• Gravity Effects on Information Filtering and Network Evolving
• The rigorous solution for the average distance of a Sierpinski network
• Zero-temperature Glauber dynamics on small-world networks
• Temporal complex networks modeling applied to vehicular ad-hoc networks
• Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness
• Complex systems: features, similarity and connectivity
• Information inequalities and Generalized Graph Entropies
• Connectivity and Dynamics of Neuronal Networks as Defined by the Shape of Individual Neurons
• Universality of eigenvector delocalization and the nature of the SIS phase transition in multiplex networks
• Bayesian Reasoning in Eternal Inflation: A Solution to the Measure Problem
• Temperature dependent network stability in simple alcohols and pure water: the evolution of Laplace spectra
• Analyzing Trails in Complex Networks
• Comparative Resilience Notions and Vertex Attack Tolerance of Scale-Free Networks
• Network topology of the Argentine interbank money market
• Contrarian effects and echo chamber formation in opinion dynamics
• How Integrated are Theoretical and Applied Physics?
• Minimal paths between communities induced by geographical networks
• Knowledge Acquisition by Networks of Interacting Agents in the Presence of Observation Errors
• Fast Community Identification by Hierarchical Growth
• "Clumpiness" Mixing in Complex Networks
• The relationship between structure and function in locally observed complex networks
• Variability Analysis of Complex Networks Measures based on Stochastic Distances
• Time evolution of the behaviour of Brazilian legislative Representatives using a complex network approach
• Decoupling approximation robustly reconstructs directed dynamical networks
• A Scalable Algorithm for Structure Identification of Complex Gene Regulatory Network from Temporal Expression Data
• GraphTune: A Learning-based Graph Generative Model with Tunable Structural Features
• Cliques and a new measure of clustering: with application to U.S. domestic airlines
• Bounding robustness in complex networks under topological changes through majorization techniques
• Deep Node Ranking for Neuro-symbolic Structural Node Embedding and Classification
• Designing Networks: A Mixed-Integer Linear Optimization Approach
• Heterogeneous information network model for equipment-standard system
• Degree and component size distributions in generalized uniform recursive tree
• Dynamics in cortical activity revealed by resting-state MEG rhythms
• An Image Analysis Approach to the Calligraphy of Books
• Topological street-network characterization through feature-vector and cluster analysis
• Community Structure Characterization
• Popularity and Centrality in Spotify Networks: Critical transitions in eigenvector centrality
• Low Cost Carriers induce specific and identifiable delay propagation patterns: an analysis of the EU and US systems
• Discriminating word senses with tourist walks in complex networks
• Graph machine learning for flight delay prediction due to holding manouver
• Automatic Discovery of Families of Network Generative Processes
• Rank-dependent deactivation in network evolution
• Modeling Connectivity in Terms of Network Activity
• Sensitivity of complex networks measurements
• Characterization of Large-Scale Functional Brain Networks During Ketamine-Medetomidine Anesthetic Induction
• Syntonets: Toward A Harmony-Inspired General Model of Complex Networks
• Eigenvalue Preferential Attachment Networks A Dandelion Structure
• An introduction to spectral distances in networks (extended version)
• Network Science approach to Modelling Emergence and Topological Robustness of Supply Networks: A Review and Perspective
• I will be there for you: six friends in a clique
• Computing Vertex Centrality Measures in Massive Real Networks with a Neural Learning Model
• Hierarchy, Fractality, Small-World and Resilience of Haversian Bone Structure: A Complex Network Study
• Homology Groups of Embedded Fractional Brownian Motion
• Characterizing the Diversity of Dynamics in Complex Networks Without Border Effects
• Spatio-spectral networks for color-texture analysis
• Reliability Maximization in Uncertain Graphs
• Malleability of complex networks
• On the Importance of Hubs in Hopfield Complex Neuronal Networks under Attack
• Multi-Feature Fusion-based Scene Classification Framework for HSR Images
• Analytic Solution to Clustering Coefficients on Weighted Networks
• Hypothesis Testing for Two Sample Comparison of Network Data
• Analysing Collective Behaviour in Temporal Networks Using Event Graphs and Temporal Motifs
• Social Network Processes in the Isabelle and Coq Theorem Proving Communities
• Complex Network-Based Approach for Feature Extraction and Classification of Musical Genres
• Transforming complex network to the acyclic one
• 2D pattern evolution constrained by complex network dynamics
• Dynamic texture analysis with diffusion in networks
• Language Networks: a Practical Approach
• The growing topology of the C. elegans connectome
• Maximum Leaf Spanning Trees of Growing Sierpinski Networks Models
• An epistemic approach to model uncertainty in data-graphs
• Mean field approximation for biased diffusion on Japanese inter-firm trading network
• Contour polygonal approximation using shortest path in networks
• Multilayer Complex Network Descriptors for Color-Texture Characterization
• On the effect of memory on the Prisoner's Dilemma game in correlated networks
• Neuromorphic Networks as Revealed by Features Similarity
• Link-Space and Network Analysis
• Learning an Integrated Distance Metric for Comparing Structure of Complex Networks
• Graph Operator Modeling over Large Graph Datasets
• Small world is not enough: Criteria for network choice and conclusiveness of simulations
• On the Efficiency of Data Representation on the Modeling and Characterization of Complex Networks
• Feature extraction from complex networks: A case of study in genomic sequences classification
• A survey of recent results in (generalized) graph entropies
• A decaying factor accounts for contained activity in neuronal networks with no need of hierarchical or modular organization
• On the Efficiency of Underground Systems in Large Cities
• Structure and Dynamics of Brain Lobe's Functional Networks at the Onset of Anesthesia-Induced Loss of Consciousness
• Growing Network Models Having Part Edges Removed/added Randomly
• Network analyses of student engagement with on-line textbook problems
• Shortest Paths in HSI Space for Color Texture Classification
• Complex network prediction using deep learning
• Quantitative Graph Theory: A new branch of graph theory and in network science
• A Complex Network Approach for Nanoparticle Agglomeration Analysis in Nanoscale Images
• Complex network classification using partially self-avoiding deterministic walks
• Characterizing the structure of protein-protein interaction networks
• Complex Networks of Functions
• Towards a Quantitative Theory of Digraph-Based Complexes and its Applications in Brain Network Analysis
• Graph Metrics for Internet Robustness -- A Survey
• Accessibility: A Generalization of the Node Degree (A Tutorial)
• Spatial Neural Networks and their Functional Samples: Similarities and Differences
• R&D Strategy Document
• Graph model selection by edge probability sequential inference
• Fusion of Complex Networks-based Global and Local Features for Texture Classification
• Opportunities and challenges in partitioning the graph measure space of real-world networks
• On the Separability of Attractors in Grandmother Dynamic Systems with Structured Connectivity
• Modelling China's Credit System with Complex Network Theory for Systematic Credit Risk Control
• Feature Extraction from Degree Distribution for Comparison and Analysis of Complex Networks
• Topological effects of data incompleteness of gene regulatory networks
• Two-walks degree assortativity in graphs and networks
• Multiple complex networks emerging from individual interactions
• The Function of Communities in Protein Interaction Networks at Multiple Scales
• Tourism destinations as digital business ecosystems
• Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks
• On Topological Structure of Web Services Networks for Composition
• From Cities to Series: Complex Networks and Deep Learning for Improved Spatial and Temporal Analytics*
• Phase-space networks and connectivity of the kagome antiferromagnet
• How Complex is a Complex Network? Insights from Linear Systems Theory
• Modeling Worldwide Highway Networks
• Knowledge transfer in a tourism destination: the effects of a network structure
• Learning Local Complex Features using Randomized Neural Networks for Texture Analysis
• Evaluating links through spectral decomposition
• Unveiling the Relationship Between Structure and Dynamics in Complex Networks
• Transistors: A Network Science-Based Historical Perspective
• Detección de comunidades en redes: Algoritmos y aplicaciones
• Spectral analysis for gene communities in cancer cells
• How does the Topology of City Streets Impact on their Respective Optimization?
• Guidelines for Experimental Algorithmics in Network Analysis