优化社交网络连接以提升少数群体信息获取公平性
Promoting Fairness in Information Access within Social Networks
- 用阻力距离衡量信息可达性，强调全局结构与多路径连通性
- 提出线性时间算法，百万级节点网络仍保持高精度
- 适用于改善社交平台中弱势群体的信息可见性
在线社交网络加速了信息传播，但少数群体因网络位置劣势，可能难以获取信息。本文研究通过新增连接来优化信息获取公平性的方法，以阻力距离度量信息可达性，提供关注全局结构与多路径连通性的新视角。该问题被证明为NP-hard。本文提出一种简单贪心算法，虽精度高但时间复杂度为立方级，不适用于大规模网络。作为主要技术贡献，通过新颖的近似技巧将时间复杂度降至线性。实验基于真实与合成数据集进行，结果表明该线性算法在百万级节点网络上仍可生成准确解。
原文摘要 · Abstract (English)
The advent of online social networks has facilitated fast and wide spread of information. However, some users, especially members of minority groups, may be less likely to receive information spreading on the network, due to their disadvantaged network position. We study the optimization problem of adding new connections to a network to enhance fairness in information access among different demographic groups. We provide a concrete formulation of this problem where information access is measured in terms of resistance distance, {offering a new perspective that emphasizes global network structure and multi-path connectivity.} The problem is shown to be NP-hard. We propose a simple greedy algorithm which turns out to output accurate solutions, but its run time is cubic, which makes it undesirable for large networks. As our main technical contribution, we reduce its time complexity to linear, leveraging several novel approximation techniques. In addition to our theoretical findings, we also conduct an extensive set of experiments using both real-world and synthetic datasets. We demonstrate that our linear-time algorithm can produce accurate solutions for networks with millions of nodes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。