PaperlayerView exact revision on arXiv

Source-linked AI summary

Link prediction in complex networks via fusing node centrality and local similarity indices: a fair-protocol reassessment and parameter design principles

Yingying Zhang, Chengye Zhao

arXiv:2609.09658v3cs.SI

TL;DR

Local similarity fusion is a proposed remedy for zero scores on pairs without common neighbors, but prior studies use heterogeneous protocols and the robustness of their gains is unclear. The paper tests a unified modulation-and-completion framework under exhaustive evaluation, finding contrasting PageRank and normalized DomiRank outcomes. Its design rules distinguish the parameter choices for the two mechanisms.

  • Problem

    Local indices score pairs without common neighbors as zero, while centrality-fusion studies use heterogeneous protocols and lack unified parameter guidance.

    Source: §1 · pp. 2–3

  • Method

    The paper studies a piecewise fusion rule that modulates local scores when information exists and completes zero scores with a centrality product.

    Source: §1 · p. 3, §2.2 · p. 5

  • Results

    All seven normalized DomiRank fused indices improve significantly at the fold level (p ≤ 3.3 × 10^-3); DR-RA averages AUC 0.9257, surpassing nine methods and comparable to RWR.

    Source: §7.1 · p. 26

  • Takeaways & Limitations

    The design rules set completion c ≤ 0.3, modulation weight ω in [0.5, 12], and DomiRank competition intensity near critical, with the two fusion doses designed separately.

    Source: §1 · p. 4

    The networks contain at most 7066 nodes, so conclusions and computational scalability on networks of 10^4 nodes or more remain unverified.

    Source: §6.2 · p. 25

Abstract

from arXiv · show

Local similarity indices assign zero scores to node pairs without common neighbors, which limits link prediction in sparse networks; fusing node centrality with local similarity is a common remedy, but existing fusion studies use heterogeneous protocols and the robustness of their gains is unclear. Within a unified piecewise fusion framework (multiplicative modulation when local information is sufficient, small-dose completion when it is absent), we show that the dynamic range of the centrality product governs the modulation mechanism: the PageRank product is of order O(n^-2), so its factor degenerates to a near-identity map. Under a fair protocol with exhaustive negative-sample comparison on eight real-world networks, PageRank fusion therefore yields no consistent significant gain for six of the seven local indices; its single exception, a gain of about +0.035 on the near-tree-like wiki-Vote network, comes entirely from completion, indicating that the completion gain depends on both the fraction of zero-score node pairs and the standalone predictive power of the centrality product. The min-max normalized DomiRank product, with an O(1) range, instead gives stable gains under unified parameters (modulation weight 5, completion coefficient 0.1): all seven fused indices improve significantly at the fold level (p <= 3.3e-3), and a 10x5 repeated cross-validation confirms robustness to the randomness of fold partitions. DR-RA reaches an average AUC of 0.9257, surpassing Katz, LNB, CN2D, CNC, CND, SimRank, CCPA, Gravity and CNPop, and comparable to RWR. The design rules obtained for the two mechanisms (completion coefficient at most 0.3, modulation weight in [0.5,12], competition intensity near critical) provide a reproducible protocol benchmark and quantitative parameter design principles for the centrality x local-similarity fusion paradigm.

1 Introduction

Local similarity fusion with node centrality is a proposed way to address local methods’ limited structural vision, but prior fusion studies lack unified parameters and consistent evaluation protocols. This study reassesses the approach and finds that centrality-product scale and information content shape fusion outcomes.

Research gap and questions

  • Existing fusion studies use index-specific weights and heterogeneous evaluation protocols, while the admissible doses for modulation and completion lack quantitative design principles.The paper frames its questions around credible evaluation, centrality properties, and parameter selection rather than proposing another fusion instance.Source: §1 · pp. 2–3

Main contributions

  • With min-max normalized DomiRank and unified parameters (ω = 5, c = 0.1), all seven fused indices improve significantly, and DR-RA outperforms nine comparison methods while matching RWR.A 10 × 5 repeated cross-validation confirms robustness to fold-partition randomness.Source: §1 · pp. 3–4
  • PageRank fusion lacks consistent significant gains for six of seven local indices; its wiki-Vote exception comes entirely from completion.The wiki-Vote gain is about +0.036, while the PA index gains +0.0000 there.Source: §1 · p. 3
  • The PageRank product is O(n^-2), making its modulation factor nearly identity, and its redundancy with preferential attachment predicts a failure boundary.On undirected networks, PageRank is approximately monotone in degree, with rank correlation above 0.89.Source: §1 · p. 3
  • The proposed design rules set completion c at most 0.3, modulation weight ω in [0.5, 12], and DomiRank competition intensity near critical.Completion depends jointly on zero-score-pair prevalence and centrality-product predictive power; modulation depends on product dynamic range.Source: §1 · p. 4

2 Preliminaries

The preliminaries contrast PageRank and DomiRank as centrality sources, then define a piecewise fusion rule that modulates local scores or completes missing local information. They identify product scale and information content, as well as parameter choice and fair negative-sample construction, as design questions.

2.1.1 PageRank (random-walk view)

  • PageRank models a random-walking user with damping and random jumps; its node scores form a probability distribution and are typically O(1/n).The paper links that score scale to the scale of the pairwise PageRank product used in fusion.Source: §2.1.1 · p. 4

2.1.2 DomiRank (competition-dynamics view)

  • DomiRank’s steady-state vector balances local and mesoscale information through competition intensity σ, and is min-max normalized to [0, 1] before fusion.Small σ emphasizes local features such as direct-neighbor counts; increasing σ emphasizes position in whole-network competition.Source: §2.1.2 · pp. 4–5

2.1.3 Duality of the two centralities and their fusion roles

  • Both centralities provide a global node-pair score by multiplying node values, but PageRank’s product is O(n^-2) while normalized DomiRank’s is O(1).This contrast motivates testing whether product scale governs fusion effectiveness.Source: §2.1.3 · p. 5

2.2 The fusion paradigm: general framework and design questions

  • The fusion rule multiplies nonzero local scores by a centrality-based factor and adds a small centrality-product completion when local scores are zero.The Charikhi method is the special case using PageRank, c = 5, and per-index ω values.Source: §2.2 · p. 5
  • Fusion design asks how to scale the centrality product, select unified ω and c, and construct negative samples without circular evaluation.The framework’s cost is dominated by the chosen centrality index.Source: §2.2 · p. 5

3 Similarity indices and experimental design

The study pairs seven local similarity indices with global and advanced comparison methods, evaluates them on eight real-world networks, and uses five-fold AUC and exhaustive negative comparisons. Its protocol also records fold-level variation and applies paired significance tests with dataset-level and multiple-testing checks.

3.1 Local similarity indices

  • The local baselines include CN, AA, RA, JC, HPI, and SO, which use common neighbors in different ways; SO and JC have identical rank-based AUCs.PA instead measures connection propensity from the two node degrees without using common neighbors.Source: §3.1 · p. 6

3.2 Global and advanced baseline indices

  • The comparison set includes global methods such as Katz, RWR, and SimRank, plus advanced indices including LNB, CN2D, CNC, and CND.The study also includes centrality-based or gravity-style baselines such as CCPA and Gravity.Source: §3.2 · pp. 6–7

3.3 Datasets

  • Eight real-world datasets are treated as unweighted, undirected graphs with self-loops removed and largest connected components retained; sizes span 105 to 7066 nodes, average degree 4.82 to 43.69, and clustering 0.142 to 0.741.ca-GrQc, facebook combined, and wiki-Vote have more than 10^3 nodes; email-Eu-core has 986 nodes.Source: §3.3 · pp. 7–8

3.4 Evaluation methodology

  • Five-fold cross-validation records per-fold AUCs, and Precision@L complements global ranking quality by measuring test-edge share among the top-L candidates.AUC compares probe links with nonexistent links; 0.5 corresponds to random guessing.Source: §3.4 · p. 8
  • Each fold compares probe edges exhaustively against all eligible non-links, with no subsampling or score-based filtering, and fixed seeds make results reproducible.Paired fold-level Wilcoxon tests are supplemented by dataset-level tests and Benjamini–Hochberg correction.Source: §3.4 · pp. 8–9

4 A fair-protocol reassessment of PageRank fusion

The section reassesses Charikhi-style PageRank fusion under a fair protocol, then uses scale-treatment controls to distinguish calibration from information content as drivers of fusion. Unnormalized PageRank fusion shows no consistent cross-network gain, while the controls indicate that normalization alone is insufficient.

4.2 Scale analysis: why the multiplicative factor is nearly identity

  • The PageRank product is O(n−2), making modulation nearly identity; with ωMD ≤2, local scores change by at most 0.02% relatively.The completion term instead orders zero-score pairs, and sweeping ω leaves mean ∆AUC unchanged at +0.00068.Source: §4.2 · p. 9

4.3 Reassessment results

  • Across eight networks, only PR-PA significantly improved over its local baseline (+0.0004; p = 2.5×10−5); the other six fused indices were non-significant.Table 2 reports the fair-protocol AUC comparison of local and PR-MD indices.Source: Table 2 · p. 10, §4.3 · p. 10

4.4 Control experiments on scale treatment: normalization is necessary but not sufficient

  • These conclusions apply to unnormalized PageRank scores under the original Charikhi protocol, not to PageRank centrality generally.The controls identify comparable product scale and low collinearity with local information as joint conditions for an effective fusion carrier.Source: §4.2 · p. 10, §4.4 · pp. 12–13

4.3 Reassessment results

  • On wiki-Vote, six common-neighbor indices gained +0.0353 ∼+0.0360, while PA gained only +5×10−6, indicating that the exception came from completion.The completion term does not depend on the local index; PA has no completion branch.Source: §4.3 · p. 11

4.4 Control experiments on scale treatment: normalization is necessary but not sufficient

  • Scale calibration activated modulation, but normalized PageRank and degree-product controls still lacked consistent gains because their information overlapped strongly with degree.The order-preserving arm improved JC/HPI/SO by +0.0017, +0.0043 and +0.0019, while the six common-neighbor indices remained non-significant.Source: §4.4 · p. 12
  • Min-max normalization changed product ordering as well as scale; order-preserving scaling retained the original product ordering and outperformed min-max on all seven indices.For HPI, the gains were +0.0043 versus +0.0004; for CN, −0.0036 versus −0.0082.Source: §4.4 · p. 12

5 DomiRank-based fusion and parameter design

The section establishes unified DomiRank fusion parameters and evaluates their performance, mechanisms, and protocol dependence. DR-RA outperforms nine comparison methods and ties RWR overall, while its gains over local baselines do not survive degree-corrected sampling.

5.1 Method definition

  • DomiRank similarity uses min-max-normalized node values, giving the centrality product a dynamic range of O(10^-2–1) for substantive modulation and controlled completion.The illustrative DR-CN example assigns a nonzero score to a pair without common neighbors.Source: §5.1 · p. 13, Figure 2 · p. 14

5.2 Unified parameters: grid search and design space

  • The selected unified parameters are ω = 5 and c = 0.1; the design analysis supports 0 < c ≤0.3 and a broad modulation plateau ω ∈[0.5, 12].The parameters use a maximin criterion; at c = 0, DR-RA's gain turns slightly negative, so modulation alone does not sustain improvement for every index.Source: §5.2 · pp. 14–15, Table 4 · p. 16

5.3 Main results

  • All seven DR-MD indices improve significantly over local baselines at the fold level (p ≤3.3×10^-3), with mean gains from +0.0011 for PA to +0.0094 for SO.Dataset-level significance concentrates on JC/SO/HPI; the result applies to exhaustive-negative sampling, and the gains do not survive degree-corrected sampling.Source: §5.3 · pp. 16–17, Table 5 · p. 17
  • Repeated 10×5 cross-validation preserves the single-partition gain signs across all eight networks, supporting robustness to fold-partition randomness.DR-CN and DR-RA gains remain positive on six networks and negative on Jazz and Wiki across repetitions.Source: §5.3 · p. 18

5.4 Comparison with global and advanced methods

  • DR-RA significantly outperforms nine comparison methods (p ≤1.8×10^-3) and is overall tied with RWR (mean −0.0003, p = 0.54).Its average AUC is higher by 0.0079–0.0702 than the nine methods; Table 7 and Figure 5 present the comparison.Source: §5.4 · p. 19, Table 7 · p. 19, Figure 5 · p. 19

5.5 Parameter sensitivity: the near-critical plateau of the competition intensity

  • DomiRank competition intensity has a near-critical safe interval of [0.7, 0.95]σ*, while performance drops markedly at σ ≥1 and can fall below baseline when σ is too small.The study uses σ = 0.85, within the stationary peak region.Source: §5.5 · p. 20, Figure 6 · p. 21

5.6 Mechanism decomposition: differentiated contributions of completion and modulation

  • At c = 0.1, completion alone improves all six common-neighbor-dependent indices by about +0.0046–+0.0049, while modulation nearly doubles gains for JC/SO/HPI.PA has no zero branch and is unaffected by pure completion; the two mechanisms together explain the full model's gains across all seven indices.Source: §5.6 · pp. 21–22, Table 9 · p. 21

5.7 Degree-corrected benchmark: which gains survive

  • Under degree-corrected sampling, gains over local baselines shift from +0.0011–+0.0094 to −0.0117–+0.0006, while DR-RA remains above the degree-only reference in all 40 fold pairs.The paper limits its all-seven significant-improvement claim to the standard protocol; under degree correction, DR-RA is thirteenth among 31 methods in panel average.Source: §5.7 · pp. 22–23, Table 10 · p. 23, Table 11 · p. 23

6 Discussion

Fusion effectiveness depends jointly on centrality-product scale and information redundancy, while completion and modulation require separate dose choices. The authors also bound their conclusions by network size, evaluation protocol, and topology.

6.1 Why unnormalized PageRank fusion fails: scale calibration, information content and the dual-mechanism division of labor

  • PageRank’s O(n^-2) product makes modulation nearly identity, and its high degree redundancy limits consistent gains; effective modulation needs comparable scale and nonredundant information.The discussion cautions that these conclusions concern unnormalized PageRank scores in the original Charikhi protocol, not PageRank centrality generally.Source: §6.1 · pp. 23–24
  • On wiki-Vote, completion gains depend jointly on zero-score-pair prevalence and standalone centrality-product prediction, while modulation can help or hurt depending on product range and redundancy.Wiki-Vote has a 0.89 zero-score fraction and a +0.036 PageRank-completion gain, whereas DomiRank modulation yields a net −0.007 across its seven indices there.Source: §6.1 · p. 24

6.2 Limitations

  • The tested networks span 105–7066 nodes, and conclusions and scalability remain unverified for networks of 10^4 nodes or more.The authors identify medium-scale and medium-or-lower-density networks as the applicable scenario, with gains narrowing on dense and large-scale networks.Source: §6.2 · p. 25
  • Unified parameters were selected and evaluated on the same fold partitions, leaving mild selection bias; fully nested cross-validation is identified as a more rigorous confirmation.Repeated cross-validation mitigates but does not eliminate this concern.Source: §6.2 · p. 25
  • The evaluation fixes exhaustive negative-sample comparison and a 20% probe-edge ratio, so performance under temporal splits or other sampling protocols remains untested.The authors also note that degree-corrected evaluation reverses gains over local baselines, while retaining a degree channel in the standard protocol.Source: §6.2 · p. 25

7 Conclusion and outlook

The paper reassesses centrality–local-similarity fusion and finds that normalized DomiRank yields consistent gains under its unified protocol, while unnormalized PageRank modulation is ineffective. It reports benchmark and parameter-design results, then outlines directions for broader validation and extension.

7.1 Conclusion

  • The PageRank product’s O(n^-2) scale and high degree redundancy make its modulation nearly identity, producing no consistent significant gains for six of seven local indices.The reported conclusions concern the original unnormalized PageRank protocol; normalization is necessary but not sufficient, and the scheme can alter node-product ordering.Source: §7.1 · p. 25
  • DR-RA attains an average AUC of 0.9257, surpassing Katz, SimRank, LNB, CN2D, CNC, CND, CCPA, Gravity and CNPop, and is comparable to RWR (mean −0.0003).All seven DomiRank fused indices significantly improve over their local baselines at fold level (p ≤ 3.3 × 10^-3), with 10 × 5 repeated cross-validation confirming robustness to fold-partition randomness.Source: §7.1 · p. 26
  • The min-max normalized DomiRank product has O(1) dynamic range; with ω = 5 and c = 0.1, all seven fused indices improve significantly at fold level.The paper reports DR-RA as comparable to RWR while keeping prediction-stage overhead close to local methods through offline centrality computation and O(1) lookups.Source: §7.1 · p. 26
  • Parameter design sets 0 < c ≤ 0.3, ω ∈ [0.5, 12], and σ ∈ [0.7, 0.95]σ∗, with completion and modulation doses designed separately.Completion depends on zero-score prevalence and standalone centrality-product predictive power; modulation depends on dynamic range.Source: §7.1 · p. 26

7.2 Outlook

  • Future work includes adaptive fusion-weight learning with nested cross-validation, extension to directed, weighted and temporal networks, and scalability checks for |V| > 10^4.The outlook also identifies local-score normalization and theoretical analysis of optimal fusion parameters as open problems.Source: §7.2 · p. 26
Loading 2609.09658v3…