CS Paper Radar

Disparity in Influence: A Fairness Evaluation of Centrality Measures in Complex Networks

Kirtidev Mohapatra, Harsh Vardhan Singh, Rishi Ranjan Singh, Akrati Saxena

cs.SI ·submitted 2026-11-15 19:47 UTC · v1

Abstract

Social networks are shaped by homophily-driven connections, which naturally lead to the emergence of communities with uneven sizes and influence. Such structural imbalances impact the fairness of network analysis tools, particularly centrality measures that are widely used to identify influential nodes for tasks like information diffusion and network robustness. In this work, we conduct a comprehensive assessment of fairness in centrality measures, using influence spreading across networks with heterogeneous community structures. We first analytically show that disparity is bounded by outreach; cross-community outreach is bounded by the inter-community cut; and when all seeds lie in one community, disparity approaches the normalized outreach within that community as cross-community transmission vanishes. This explains why attenuation concentrates influence in the community where diffusion starts. We further evaluate a broad spectrum of centrality measures, including local, semi-local, global, and community-aware measures, on both synthetic network generative models and real-world datasets, using the Independent Cascade and Linear Threshold Models. The results consistently show that influence tends to concentrate within larger communities, with disparities becoming more pronounced under constrained or deterministic diffusion settings. We further observe that fairness is highly sensitive to the choice of centrality measure rather than its general category. In particular, fairness-aware adaptations of PageRank demonstrate a strong balance between maximizing influence reach and maintaining equitable distribution across communities. On real networks, these conclusions are largely stable under random removal or addition of up to 3% of the edges. Our findings highlight the need to explicitly account for fairness when designing and selecting centrality-based strategies in networked systems.

Closest papers

Nearest neighbours by meaning across the whole index.

Algorithmic Fairness for Influence Maximization: A Survey of Models, Metrics, and Optimization Techniques

cs.SI ·2026-10-14 ·Shashank Sheshar Singh, Sunil Kumar Meena, Kuldeep Singh, krati Saxena
survey similarity 0.69
Abstract

Influence maximization (IM) has become a basis of modeling information spread across social networks, with applications in viral marketing, public health, and political campaigns. However, classical IM algorithms often prioritize the spread of overall influence and ignore its fairness, resulting in disadvantages for marginalized or underrepresented communities. This survey provides a detailed look at fairness-aware influence maximization, focusing on important challenges, models, and methods designed to ensure fair influence maximization. We categorize existing methods into five groups based on their fairness objectives, including parity, diversity, and utility, and discuss how they handle biased network structure, protected attributes, and seeding constraints. We also examine how fairness-aware influence maximization methods perform on real-world data to highlight the importance of combining fairness with classical influence maximization methods. By bridging the gap between influence spread and social equity, this survey lays the foundation for designing fair algorithms that ensure fair representation in large-scale diffusion processes. The survey concludes by outlining emerging trends, open challenges, and prospective future directions in the domain, highlighting the need for expertise spanning multiple disciplines.

0.07

Comparing Probabilistic Influence-Spreading Centralities to Commonly-Used Centrality Measures in Directed and Weighted Networks

cs.SI ·2026-08-19 ·Juuso Luhtala, Vesa Kuikka, Kimmo K. Kaski
similarity 0.66
Abstract

The Influence-Spreading Model (ISM) introduces three probabilistic centrality measures: out-centrality, in-centrality, and ISM betweenness centrality. Out-centrality measures the average probability that a node influences others, while in-centrality measures the average probability that others influence a node. ISM betweenness centrality measures the change in total probabilistic influence when a node is removed. These measures depend on edge transmission probabilities and allow walks up to a specified maximum length. We compare the ISM centrality measures to commonly used weighted variants of out-degree, in-degree, closeness, shortest-path betweenness, and Katz centrality in directed, weighted networks using four real-world online social networks and nine synthetic networks generated by Erdős-Rényi, navigable small-world, and directed scale-free models. For the synthetic networks, the edge probabilities are drawn from three beta distributions. We evaluate the similarity in centrality values and their ranking using Pearson correlation and Spearman's rank correlation coefficients. Results show strong correlations between the ISM out-centrality and weighted out-degree and outward Katz centrality, particularly for low edge probabilities. Conversely, relationships between the ISM in-centrality and other measures vary with network topology, sometimes yielding negative correlations. Correlations between the ISM betweenness and the shortest-path betweenness are also topology-dependent and weaken as alternative influence paths become more relevant. Overall, standard centrality measures can approximate the influence of broadcasting influence but often miss the nuances of receiving influence and probabilistic intermediary roles.

0.18

Whose Polarization Is It? Auditing Fairness in Network Polarization Measures

cs.SI cs.MA ·2026-10-15 ·Stanisław Stępień, Michalina Janik, Akrati Saxena, Radosław Michalski
similarity 0.66
Abstract

A polarization score is supposed to describe a community, not its surroundings. Yet when a minority community is embedded in a larger network, its measured polarization can rise or fall with the size and structure of the majority around it. We ask whether polarization measures are therefore fair to minorities and develop an audit built around two criteria: measurement invariance (MI), which asks whether otherwise equivalent majorities and minorities receive equivalent scores, and structural exogeneity (SE), which asks whether a minority's score changes when its surrounding majority changes. Resolution sensitivity (RS) is treated as a prerequisite for meaningful fairness assessment. We audit seven polarization measure families spanning the three network-operationalizable dimensions of polarization, introducing Network-Weighted Distance (NWD) to fill an unserved extremeness-separation combination. Across controlled synthetic networks, mechanism-isolating diagnostic topologies, and real political and communication networks, no measure passes all applicable checks. Minorities are systematically scored as more polarized than equivalent majorities. We trace this dependence to two separate channels: majority structure can alter the opinions that opinion-reading measures consume, and, on a different path, opinion-orthogonal structural change can affect the arithmetic of structural measures. Reading opinions is thus double-edged, letting contamination in when structure moves opinions but shielding the score when structure changes and opinions do not. We close with practical guidance for reporting polarization scores without inheriting these biases.

0.28

Diffusion-Induced Spatial Attention Overlapping Community Detection

cs.SI cs.LG ·2026-09-22 ·Kosti Koistinen, Vesa Kuikka, Joni Herttuainen, Matthew Hendren, Brian Holt +1 more
benchmark similarity 0.65
Abstract

Detection of overlapping communities is essential for modelling networks in which nodes participate simultaneously in multiple structural or functional groups. Existing graph neural network approaches commonly rely on local message passing, which can obscure community boundaries through smoothing and limit the representation of structurally relevant long-range dependencies. We introduce Diffusion-Induced Spatial Attention Community Detection (DISCO), a deep-learning framework that combines a structural prior derived from influence spreading dynamics, sparse multi-head attention, and non-negative community-affiliation learning. The prior identifies candidate interactions beyond immediate graph neighbours and biases attention according to their structural proximity, while a Bernoulli-Poisson edge-reconstruction objective enables overlapping community inference from node attributes and structural profiles, or both. Benchmark experiments show that DISCO performs competitively against established graph convolutional and graph attention approaches across different input configurations. To demonstrate its practical applicability, we present a proof-of-concept cybersecurity use case in which changes between community assignments inferred from consecutive communication-network snapshots provide an interpretable anomaly signal. Temporal community similarity identifies structural deviations, while node-level contributions help locate the devices associated with them. DISCO therefore provides both a flexible method for overlapping community detection and a foundation for analysing structural change in dynamic networks.

0.07

Explicit objective functions in modularity-based community detection on multiplex networks

cs.SI ·2026-09-29 ·Elizaveta Evmenova, Petr Chunaev
code/data similarity 0.64
Abstract · Revised exposition of the fusion-objective relationships; added label-free Cora external validation, fixed-weight baselines, and a reproduci…

Early, simultaneous, and late fusion combine network layers at different stages of community detection. Their modularity values consequently need not measure the same property of a partition. For normalized shared-node multiplexes, a unified comparison extends an existing two-layer identity: early fusion equals simultaneous fusion plus a weighted variance of community degree volumes. An elementary simplex argument explains simultaneous fusion's preference for single-layer weights. For a specified late-fusion construction, an additional transformation correction separates changes to the graph from changes to the objective. Exact small-network experiments and Louvain and Leiden experiments illustrate these distinctions. On label-free Cora, all objective-selected weights favor citations alone, while the fixed equal-weight mixtures achieve higher median adjusted Rand agreement with subject categories. The analysis provides a diagnostic for interpreting fusion objectives; higher objective values alone do not establish better recovery of externally defined communities.

0.38

FairPGT: Partitioned Graph Transformers for Dual-Level Fair Graph Clustering

cs.LG cs.AI ·2026-11-17 ·Siamak Ghodsi, Amjad Seyedi, Sahar Tahmasebi, Eirini Ntoutsi, Sören Auer
theorycode/data similarity 0.62
Abstract · Under review. 36 pages, 8 figures, 5 tables. Code: https://github.com/SiamakGhodsi/FairPGT

Clustering on attributed graphs can produce demographically biased clusters, particularly when communities align with protected groups. Graph transformers can amplify this bias through same-group attention, while global attention limits scalability. We propose FairPGT, a partitioned graph transformer for fair graph clustering. FairPGT restricts attention to METIS partitions and connects them through routing tokens, which divides the quadratic cost of attention by the number of partitions. A graph-aware self-training target guides clustering, with a provably bounded deviation from the standard DEC target. Fairness is imposed at two levels: a mutual-information term promotes demographic parity in cluster assignments, while a normalized cross-group attention ratio (nCGAR) guides attention toward group neutrality through self-distillation. We prove that the nCGAR correction moves attention toward neutrality and establish a condition preventing overshooting. Across seven benchmarks, FairPGT achieves the best clustering performance and statistical parity on the three largest graphs (Credit, Pokec-n, Pokec-z), with a statistical-parity gap approximately ten times lower than DMoN, and is Pareto-dominated on only one dataset. On controlled stochastic block models, FairPGT attains 97% of the derived upper bound on NMI for exactly fair clustering when communities and protected groups coincide. These graphs further show that, under strong alignment, assignment-level fairness alone makes the attention group-heterophilous, whereas attention-level fairness alone improves neutrality without ensuring fair clusters. Code for reproducibility is available at https://github.com/SiamakGhodsi/FairPGT.

0.42

Group dynamics of engagement with AI topics on Bluesky

cs.SI cs.CYphysics.soc-phstat.AP ·2026-09-28 ·Bradley Huynh, Moyi Tian, Nancy Rodríguez
similarity 0.62
Abstract · 10 pages, 4 figures, 3 tables

Social media increasingly shapes everyday life, serving as both a central venue for discussion of major events and a space where online collective behavior can spill over into real-world activity, while artificial intelligence (AI) is likewise becoming increasingly influential across society. Understanding how different online communities respond to AI-related events, and disentangling the mechanisms underlying the development of such engagement, are therefore increasingly important for studying information spreading and the societal reception of AI. Our work addresses the limited connection between empirical studies of AI-related online engagement and mathematical modeling of group-level spreading dynamics. We develop a framework to collect and organize empirical Bluesky activity into distinct user groups, then use a network-based dynamics model to investigate the mechanisms underlying their engagement. We use the release of DeepSeek R1 as a case study under two complementary grouping schemes: AI-related communities and academic disciplines. For each group, we fit a network-based Susceptible-Infected-Recovered (SIR)-type model augmented with an exogenous engagement term, allowing us to quantify the relative strengths of endogenous network-driven spreading and direct external response. Across groups, we find that strong direct responses to the event do not necessarily coincide with strong network-driven propagation, revealing distinct engagement patterns that may be obscured by aggregate activity alone.

0.12

CSBA-Net: Learning Cross-Scale Structural Dependencies for Influential Node Identification in Complex Networks

cs.SI ·2026-10-13 ·Rihab Boukheche, Mohammed Lalou, Nardjes Bouchemal
similarity 0.61
Abstract

Identifying influential nodes is a fundamental task in complex network analysis, with applications in epidemic control, information diffusion, and network robustness. Existing centrality-based and learning-based methods often provide limited integration of structural information across different network scales. To address this limitation, we propose CSBA-Net, for Cross-Scale Structural BiGRU Attention Network, a multi-scale structural representation learning framework that jointly captures local, community-level, and global structural patterns. The extracted representations are processed by CNNs and integrated through a BiGRU with multi-head self-attention to model dependencies across structural scales. Influential-node scores are learned through regression using SIR-based diffusion simulations as reference targets. We conduct experiments on 24 real-world and 12 synthetic networks from social, biological, technological, and knowledge domains, and show that CSBA-Net achieves Kendall's tau=0.802, Spearman's rho=0.943, NDCG10 =0.898, and NDCG20 =0.916, outperforming the considered centrality-, CNN-, and GNN-based baselines. The results demonstrate the effectiveness of combining complementary structural scales for accurate influential-node ranking across diverse network structures.

0.12