Subgraph Centrality in Complex Networks
arXiv:cond-mat/0504730 · doi:10.1103/PhysRevE.71.056103
Abstract
We introduce a new centrality measure that characterizes the participation of each node in all subgraphs in a network. Smaller subgraphs are given more weight than larger ones, which makes this measure appropriate for characterizing network motifs. We show that the subgraph centrality (SC) can be obtained mathematically from the spectra of the adjacency matrix of the network. This measure is better able to discriminate the nodes of a network than alternate measures such as degree, closeness, betweenness and eigenvector centralities. We study eight real-world networks for which SC displays useful and desirable properties, such as clear ranking of nodes and scale-free characteristics. Compared with the number of links per node, the ranking introduced by SC (for the nodes in the protein interaction network of S. cereviciae) is more highly correlated with the lethality of individual proteins removed from the proteome.
29 pages, 4 figures, 2 tables
References in corpus (15)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Lethality and centrality in protein networks
- The diameter of the world wide web
- The large-scale organization of metabolic networks
- Evolution of networks
- Classes of behavior of small-world networks
- Analysis of weighted networks
- The Web of Human Sexual Contacts
- Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
- Classification of scale-free networks
- Global Organization of the Lexicon
- Networks in life: Scaling properties and eigenvalue spectra
Cited by in corpus (134)
- Characterization of complex networks: A survey of measurements
- Vital nodes identification in complex networks
- Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
- Communicability in complex networks
- The Physics of Communicability in Complex Networks
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- Complex Networks as Hypergraphs
- Consistency and differences between centrality measures across distinct classes of networks
- Virtual Identification of Essential Proteins Within the Protein Interaction Network of Yeast
- Spectral Measures of Bipartivity in Complex Networks
- Understanding the spreading power of all nodes in a network: a continuous-time perspective
- Network Analysis of Particles and Grains
- Statistical-mechanical approach to subgraph centrality in complex networks
- On dynamic network entropy in cancer
- Spectral centrality measures in complex networks
- Communicability Betweenness in Complex Networks
- Graph Vulnerability and Robustness: A Survey
- The Influence of Network Topology on Sound Propagation in Granular Materials
- On the limiting behavior of parameter-dependent network centrality measures
- Spectral Scaling in Complex Networks
- A Survey on Centrality Metrics and Their Implications in Network Resilience
- Approximating Spectral Impact of Structural Perturbations in Large Networks
- Two betweenness centrality measures based on Randomized Shortest Paths
- Identifying effective multiple spreaders by coloring complex networks
- Machine Learning in Network Centrality Measures: Tutorial and Outlook
- Exploiting symmetry in network analysis
- Congestion-gradient driven transport on complex networks
- Multiscale characterization of recurrence-based phase space networks constructed from time series
- Analyzing complex networks through correlations in centrality measurements
- Modelling Non-Linear Consensus Dynamics on Hypergraphs
- Detecting global bridges in networks
- Systematic comparison between methods for the detection of influential spreaders in complex networks
- An Analysis of Centrality Measures for Complex and Social Networks
- Random Walks Along the Streets and Canals in Compact Cities: Spectral analysis, Dynamical Modularity, Information, and Statistical Mechanics
- International Trade Network: Country centrality and COVID-19 pandemic
- Global Value Trees
- Unraveling the effects of multiscale network entanglement on disintegration of empirical systems
- A general centrality framework based on node navigability
- Continuous-Time Quantum Search on Balanced Trees
- Path Integral Based Convolution and Pooling for Graph Neural Networks
- A Review of Features for the Discrimination of Twitter Users: Application to the Prediction of Offline Influence
- Functional centrality in graphs
- Analysis of relative influence of nodes in directed networks
- A literature survey of matrix methods for data science
- Pre-Training Graph Neural Networks for Generic Structural Feature Extraction
- Mittag-Leffler functions and their applications in network science
- Influence maximization on temporal networks
- Concentric Characterization and Classification of Complex Network Nodes: Theory and Application to Institutional Collaboration
- Objective measures for sentinel surveillance in network epidemiology
- Maximum Estrada Index of Bicyclic Graphs
- Fast computation of matrix function-based centrality measures for layer-coupled multiplex networks
- A Matrix Hyperbolic Cosine Algorithm and Applications
- Ranking by Loops: a new approach to categorization
- Community structure in the World Trade Network based on communicability distances
- A measure of centrality based on the spectrum of the Laplacian
- A Network Science perspective of Graph Convolutional Networks: A survey
- Data-driven modeling of collaboration networks: A cross-domain analysis
- Scale-dependent measure of network centrality from diffusion dynamics
- Discovering Network Structure Beyond Communities
- Conversational Networks for Automatic Online Moderation
- Fractional-order susceptible-infected model: definition and applications to the study of COVID-19 main protease
- Orientations and matrix function-based centralities in multiplex network analysis of urban public transport
- Algebraic combinatorics on trace monoids: extending number theory to walks on graphs
- On the stability of network indices defined by means of matrix functions
- Path-dependent connectivity, not modularity, consistently predicts controllability of structural brain networks
- Pattern-detection in the global automotive industry: a manufacturer-supplier-product network analysis
- Finding the Resistance Distance and Eigenvector Centrality from the Network's Eigenvalues
- Graph Energies of Egocentric Networks and Their Correlation with Vertex Centrality Measures
- Mathematical Modeling of Local Balance in Signed Networks and Its Applications to Global International Analysis
- Organization Mining Using Online Social Networks
- Measuring nodes centrality when local and global measures overlap
- Identifying sparse and dense sub-graphs in large graphs with a fast algorithm
- Exploring the "Middle Earth" of Network Spectra via a Gaussian Matrix Function
- Subgraphs and motifs in a dynamic airline network
- Random-Graph Models and Characterization of Granular Networks
- A Fast Frequent Directions Algorithm for Low Rank Approximation
- Where to cut to delay a pandemic with minimum disruption? Mathematical analysis based on the SIS model
- "Clumpiness" Mixing in Complex Networks
- Centralities in Simplicial Complexes
- A Centrality Measure for Cycles and Subgraphs II
- What do we learn from correlations of local and global network properties?
- Selection of Centrality Measures Using Self-Consistency and Bridge Axioms
- The trace and Estrada index of uniform hypergraphs with cut vertices
- Centralities in complex networks
- Real-Space Visualization of Quantum Phase Transition by Network Topology
- Graph Theory and Networks in Biology
- Discriminating Power of Centrality Measures
- Cycle-centrality in complex networks
- Decoding asymptomatic COVID-19 infection and transmission
- Robustness of Regular Graphs Based on Natural Connectivity
- A Fast Monte Carlo algorithm for evaluating matrix functions with application in complex networks
- About the Discriminant Power of the Subgraph Centrality and Other Centrality Measures About the Discriminant Power of the Subgraph Centrality and Other Centrality Measures(Working paper)
- The von Neumann entropy of networks
- Bounds For The Distance Estrada Index Of Graphs
- A mixed clustering coefficient centrality for identifying essential proteins
- Geometry of Complex Networks and Topological Centrality
- Potential gain as a centrality measure
- Influence measures in subnetworks using vertex centrality
- Adjustable reach in a network centrality based on current flows
- Eigenvalue Preferential Attachment Networks A Dandelion Structure
- Review of COVID-19 Antibody Therapies
- Discovering Interesting Subgraphs in Social Media Networks
- Vertex distinction with subgraph centrality: a proof of Estrada's conjecture and some generalizations
- The trace of uniform hypergraphs with application to Estrada index
- The effect of the pandemic on complex socio-economic systems: community detection induced by communicability
- How to choose the most appropriate centrality measure? A decision tree approach
- New results and open problems on subgraph centrality
- Computational Human Dynamics
- Analysing Motifs in Multilayer Networks
- Characterizing SARS-CoV-2 mutations in the United States
- Maximizing spreading in complex networks with risk in node activation
- Can you always reap what you sow? Network and functional data analysis of VC investments in health-tech companies
- Two new methods for identifying proteins based on the domain protein complexes and topological properties
- A graph theoretic approach for modelling wildlife corridors
- Communicability Angle and the Spatial Efficiency of Networks
- More on the normalized Laplacian Estrada index
- Geracao Automatica de Paineis de Controle para Analise de Mobilidade Urbana Utilizando Redes Complexas
- Two-walks degree assortativity in graphs and networks
- New lower bounds for the Estrada and Signless Laplacian Estrada Index of a Graph
- An increasing sequence of lower bounds for the Estrada index of graphs and matrices
- Automatic Text Document Summarization using Semantic-based Analysis
- Spectral signatures of structural change in financial networks
- On the distribution of topological and spectral indices on random graphs
- Statistics of remote regions of networks
- Centrality of nodes in Federated Byzantine Agreement Systems
- A Query-Driven System for Discovering Interesting Subgraphs in Social Media
- Calibratable Hetero-NodeRank for measuring node influence
- Centrality Meets Centroid: A Graph-based Approach for Unsupervised Document Summarization
- Some New Lower Bounds for the Estrada Index
- Accounting for the Role of Long Walks on Networks via a New Matrix Function
- Differentially Categorized Structural Connectome Hubs are Involved in Differential Microstructural Basis and Functional Implications and Contribute to Individual Identification
- A network theoretic study of ecological connectivity in Western Himalayas
- On maximum Estrada indices of bipartite graphs with some given parameters
- A statistical mechanics description of environmental variability in metabolic networks