提出新算法在加权多层网络中高效计算节点重要性,避免信息丢失。
Degree Centrality Algorithms for Weighted Multilayer Networks (or w-MLNs)

- 分层独立分析,不合并成单层图,保留原始结构
- 启发式算法精度接近真实结果,速度提升显著
- 适合处理带权重的多关系网络,如社交或生物网络
中心性度量通常用于简单图(有向、无向、加权或未加权)。当涉及多种关系的应用使用多层网络(MLNs)建模时,传统方法需将多层网络简化为单层图,导致结构和语义信息损失,尤其在加权网络中更为严重。本文聚焦于加权同质多层网络(HoMLNs)中的度中心性计算,提出基于解耦框架的方法。该框架对各层进行独立分析,无需将多层网络降维为简单图,仅利用各层最小信息即可计算整体度中心性。我们设计了启发式算法,在准确性和效率间取得平衡。实验在合成与真实世界HoMLN数据集上验证,结果表明,所提方法精度接近布尔或聚合基线(GT),同时大幅提高计算效率,证明了该解耦方法在可扩展性与有效性上的优势。
原文摘要 · Abstract (English)
Centrality measures are defined for simple graphs -- directed, undirected, weighted or unweighted. Attributed graphs have to be reduced to simple graphs for computing centrality measures. However, when applications with multiple types of relationships are modeled using multilayer networks (MLNs), simple graph algorithms cannot be directly used. Existing approaches typically analyze MLNs by aggregating layers of an MLN into a single graph, which results in the loss of structural and semantic information. The semantic information loss can be more pronounced particularly, in weighted networks. This work focuses on computing degree centrality in weighted homogeneous multilayer networks (HoMLNs) using a decoupling-based framework. The framework performs independent layer-wise analysis on MLNs without reducing them to simple graphs. The decoupling approach allows use of exiting algorithms for each layer and uses minimal information from individual layers for computing degree centrality of HoMLNs. We propose heuristic-based algorithms that strike a balance between accuracy and efficiency. The proposed methods are evaluated against ground truth (GT) results obtained using Boolean OR aggregation and naive baselines. Experimental results on both synthetic and real-world HoMLN datasets demonstrate that the heuristics achieve accuracy comparable to the ground truth while significantly improving computational efficiency, thereby establishing the scalability and effectiveness of the HoMLN algorithms developed using the decoupling approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。