Interconnectedness coefficient identifies key connectors in network regions
The Interconnectedness Coefficient: A Semi-Local Graph-Theoretic Measure for Connector Vertices between Cohesive Network Regions
Social and Information Networks
Summary
Networks often have tight groups of nodes connected closely together, and some special nodes act like bridges between these groups. The authors introduce the interconnectedness coefficient, a new way to find these bridge-like nodes using information from nearby parts of the network. Their method doesn’t need to know the full groups beforehand and works well in biological networks like protein interactions. This helps highlight important connector proteins that link molecular complexes.
What this means in practice
- •For systems biology teams: Identify proteins that act as connectors between molecular complexes by using the interconnectedness coefficient in protein interaction networks.
- •For network analysts: Detect bridging nodes between cohesive sub-networks without needing predefined community partitions, improving network structure understanding.
Tested on one dataset.
Authors
Thomas Wiebringhaus
Abstract
The Interconnectedness Coefficient (IC) is a bounded semi-local graph-theoretic node measure designed to identify connector vertices between cohesive network regions. Such connector vertices, also referred to as bridging nodes, may mediate between locally cohesive regions even when they are neither hubs nor themselves highly clustered. The IC preferentially assigns high values to weakly clustered focal vertices whose adjacent vertices remain strongly clustered after exclusion of the focal connection. Candidate vertices are required to have degree at least two. The construction is partition-free, uses information within radius two, and requires no predefined community or module partition. The range and extremal properties of the score are derived analytically. Exact graph families isolate its maximal response to fully cohesive branches, its controlled response to a single cohesion defect, its invariance under a cohesion-free hub extension, and a sharp fragmentation threshold. A separate application to a Human Interactome Map reveals pronounced degree-dependent stabilization of IC values near the network's mean clustering level. This behavior follows directly from the multiplicative definition. If focal clustering tends to zero while mean leave-one-out cohesion in the neighborhood stabilizes, the IC converges to that neighborhood-cohesion level. Among the highly ranked IC vertices are proteins with established interface, scaffold, and adaptor roles in molecular complexes. The IC is therefore positioned as a semi-local connector measure for cohesive network regions.