PaperlayerView exact revision on arXiv

Source-linked AI summary

A Novel Measure of Edge Centrality in Social Networks

Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, Angela Ricciardello

arXiv:1303.1747v1cs.SIcs.DSphysics.soc-ph

TL;DR

Identifying important network nodes and edges requires centrality measures, but local measures may be unfaithful and exact computation can be costly. The paper introduces κ-path edge centrality using bounded random walks and an O(κm) algorithm. It reports that the method is feasible on large social networks, while noting that consistent score distributions across runs do not ensure the same edges receive matching scores.

  • Problem

    Local centrality measures may be unfaithful, exact centrality computation is costly on growing networks, and shortest-path-only propagation may not reflect information flow.

    Source: §1 · p. 1

  • Method

    The paper defines κ-path edge centrality by treating frequently used information-diffusion edges as central and simulating simple random walks bounded by κ.

    Source: §1 · p. 2

  • Results

    The algorithm runs in O(κm) worst-case time and the authors report that it is feasible on large real-life social networks.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Edges frequently exploited to diffuse information provide a measure of their importance within a social network.

    Source: §1 · p. 2

    Consistent centrality-value distributions across runs do not ensure that the same edges receive the same or similar values across runs.

    Source: §4.1.1 · p. 13

Abstract

from arXiv · show

The problem of assigning centrality values to nodes and edges in graphs has been widely investigated during last years. Recently, a novel measure of node centrality has been proposed, called k-path centrality index, which is based on the propagation of messages inside a network along paths consisting of at most k edges. On the other hand, the importance of computing the centrality of edges has been put into evidence since 1970's by Anthonisse and, subsequently by Girvan and Newman. In this work we propose the generalization of the concept of k-path centrality by defining the k-path edge centrality, a measure of centrality introduced to compute the importance of edges. We provide an efficient algorithm, running in O(k m), being m the number of edges in the graph. Thus, our technique is feasible for large scale network analysis. Finally, the performance of our algorithm is analyzed, discussing the results obtained against large online social network datasets.

1. Introduction

The introduction motivates edge centrality as a way to identify important actors and ties, while noting that exact centrality computation can be costly and shortest-path assumptions may not fit information propagation. It presents κ-path edge centrality, computed through bounded random walks, and an O(κm) algorithm intended for large networks.

1. Introduction

  • Local centrality measures are computationally feasible on large networks but may be unfaithful, while exact centrality computation becomes demanding as networks grow.The introduction also questions whether information always propagates along shortest paths.Source: §1 · pp. 1–2
  • An edge is considered central when it is frequently used to diffuse information through the network.The approach frames edge-centrality computation as information propagation.Source: §1 · p. 2
  • The simulated walks are simple and bounded by user-defined κ, reflecting the assumptions that edges are not revisited and more distant nodes influence each other less.The distance-related assumption is attributed to.Source: §1 · p. 2
  • The paper extends κ-path centrality to edges using random walks of up to κ edges, presented as the first random-walk approach to edge centrality.The introduction contrasts the limited edge-centrality literature with prior uses of random walks for node centrality.Source: §1 · p. 2
  • O(κm) worst-case time makes the algorithm linear in edge count, unlike exact centrality methods cited as running in O(n^3) or, with optimizations, O(nm).The authors report that it works on large real-life social networks, including under limited computing resources.Source: §1 · p. 3
  • Experiments show that κ-path edge centrality yields reproducible results despite relying on random walks, is feasible on large social networks, and has properties discussed to characterize the studied networks.Source: §1 · p. 3

2. Background about Centrality Measures and Applications

This background section reviews centrality measures and their applications, including shortest-path approaches, computationally costly betweenness methods, and random-walk alternatives. It also describes how centrality information is used in social-network applications.

2. Background about Centrality Measures and Applications

  • The section surveys centrality measures and recent approaches for computing them.It covers measures and applications in social-network analysis.Source: §2 · p. 3

2.1. Centrality Measure in Social Networks

  • Betweenness centrality assigns importance according to shortest paths, but shortest-path-only propagation may not reflect influence, and applications may need only the most relevant portion of a ranking.For edges, Anthonisse’s rush index measures an edge’s share of shortest-path flow between node pairs.Source: §2.1 · pp. 3–4

2.2. Recent Approaches for Computing Betweenness Centrality

  • Exact betweenness algorithms can be costly on large networks, motivating approximate methods including randomized algorithms and random-walk approaches such as κ-path centrality for nodes.The cited RA-κpath algorithm runs in O(κ^3 n^(2−2α) log n).Source: §2.2 · p. 4

2.3. Application of Centrality Measures in Social Network Analysis

  • Social-network centrality has been applied to marketing, recommendation, and trust analysis, while high-κ-path-centrality edges may identify important ties and information routes.The cited applications include finding channels for information distribution and studying influence spread.Source: §2.3 · p. 5

3. Measuring Edge Centrality

This section defines κ-path edge centrality and presents a simulation-based algorithm that estimates it through bounded message-propagation random walks and edge-weight updates. It also describes decentralized modeling of information flows and the use of edge strength for link prediction.

3.1. Design Goals

  • The design calls for random walks because devices know only their contacts, dynamic edge rankings that reward frequently selected links, simple paths, and a maximum path length κ.The length bound reflects the view that distant nodes influence one another less.Source: §3.1 · p. 6

3.2. κ-Path Centrality

  • κ-path edge centrality sums, over source nodes, the frequency that messages traverse an edge along random simple paths of at most κ edges.Directly counting all such paths may be infeasible because their number can be exponential in the graph’s node count.Source: §3.2 · p. 7

3.3. The Algorithm for Computing the κ-Path Edge Centrality

  • ERW-KPath and WERW-KPath each assign node and edge weights, then simulate message propagation on random simple paths; their selection probabilities are uniform or weighted, respectively.Both algorithms are described as returning an approximate value of the edge centrality defined in the section.Source: §3.3 · p. 7

3.3.1. Step 1: node and edge weights assignment

  • The first algorithm stage assigns node weights for selecting message sources and edge weights as initial centrality values that are updated during execution.Source: §3.3.1 · p. 8

3.3.2. Step 2: Simulation of message propagations through random simple κ-paths

  • With ρ=|E|−1, the algorithm runs in worst-case O(κ|E|), and is near-linear in |V| when |E| is of the same order.Each traversed edge receives a bonus, while the walk is limited to κ edges and cannot reuse an edge.Source: §3.3.2 · pp. 9–10

3.4. Novelties introduced by our approach

  • The approach allows alternative source- and receiver-selection strategies, and its unicast propagation model can be modified to support multicast.The presented source strategies are uniform selection and selection proportional to node degree.Source: §3.4 · p. 11
  • Unlike information centrality, which relies on shortest paths and network-efficiency drops, this approach estimates edge centrality from random-walk message frequency in a decentralized network and scales nearly linearly with edges.Source: §3.4 · p. 11
  • Although message propagation requires edge orientation, both algorithms induce that orientation from each source-to-recipient message and can therefore operate on undirected networks.Source: §3.4 · p. 11

3.5. Comparison of the ERW-Kpath and WERW-Kpath algorithms

  • Both ERW-Kpath and WERW-Kpath correctly approximate the κ-path centrality values defined in the paper.Source: §3.5 · p. 11
  • WERW-Kpath is preferred because it weights edge-selection probabilities by past message frequency, helping identify preferential information flows that ERW-Kpath may miss.ERW-Kpath assumes nodes can select any unselected edge at random, an assumption described as potentially too strong for real social networks.Source: §3.5 · pp. 11–12
  • WERW-Kpath can support link prediction by using edge weights to quantify relationship strength and computing measures such as Jaccard only over edges above a chosen threshold.Filtering rarely used edges produces a Jaccard coefficient based on strong edges.Source: §3.5 · p. 12

4. Experimentation

Experiments assess WERW-Kpath’s robustness, performance, and edge-centrality distributions across online social-network datasets. Results show highly overlapping runs and near-linear execution scaling, while larger κ improves discrimination but increases computational cost.

4. Experimentation

  • The experiments use datasets representing Wikipedia voting, arXiv paper networks, scientific citations, a Facebook friendship sample, and a YouTube graph fragment.The datasets are summarized in Table 1.Source: §4 · p. 12, Table 1 · p. 13

4.1. Robustness

  • The evaluation examines both consistency across repeated runs with the same configuration and whether changing κ affects edge rankings.The robustness tests use quantitative distribution comparisons and a separate qualitative analysis of rankings.Source: §4.1 · pp. 12–13

4.1.1. Quantitative analysis of results

  • Across datasets, centrality-value distributions almost completely overlapped across runs, but this did not establish that individual edges retained corresponding values.On Wiki-Vote, Figure 2 shows four same-configuration runs; similar distribution overlap was reported for the other considered datasets.Source: §4.1.1 · p. 13, Figure 2 · p. 14

4.1.2. Qualitative analysis of results

  • Across collaboration, citation, and online-community datasets, results remained highly overlapping; increasing κ and tolerance strengthened overlap and Pearson correlation.Euclidean distances were no larger than [10−2, 10−3], with average distance around [10−7, 10−10].Source: §4.1.2 · pp. 15–16

4.2. Performance

  • Figure 3 shows execution scaling almost linearly with network edge count and configured κ, supporting feasibility on large networks where exact edge-betweenness is costly.The authors identify κ = 20 as a trade-off between edge discrimination and computational cost.Source: §4.2 · p. 16, Figure 3 · p. 17, §4.3 · p. 18

4.3. Analysis of Edge Centrality Distributions

  • Log-scaled distributions followed a power law: few edges had high centrality, while many were low, as frequently selected edges received more updates.The authors attribute the distribution to frequent random-walk selection of some edges and infrequent selection of many others.Source: §4.3 · p. 17
  • Increasing κ raises centrality scores and sharpens high/low-edge separation, but increases O(κm) cost; κ = 20 is a trade-off, while rankings largely persist across κ settings.The reported ranking stability means uncertainty in tuning κ does not have a devastating impact on identifying the highest-ranked edges.Source: §4.3 · p. 18

5. Applications of our approach in Knowledge-Based systems

The section outlines three potential Knowledge-Based Systems applications: organizing data through community detection, finding associations in semantic networks, and understanding relationships in virtual communities.

5.1. Data Clustering

  • Edge ranking can support graph community detection, while Girvan–Newman’s computational cost limits its use on repositories containing millions of objects.The section motivates graph representations where edges encode relationships between data points, avoiding cases where pairwise distances are costly or meaningless.Source: §5.1 · pp. 18–19
  • Communities could group users with shared interests or help retrieve content related to query-matched objects, including items users may not know exist.The section proposes mapping user-generated content to a graph and retrieving objects in the same community as those matched by a query.Source: §5.1 · pp. 20–21

5.2. Semantic Web

  • For semantic networks, the authors plan to use bounded random walks instead of shortest paths to discover associations and compare result quality against shortest-path approaches.The proposed setting includes heterogeneous objects and relationship types, as in RDF knowledge bases.Source: §5.2 · p. 21

5.3. Understanding user relationships in virtual communities

  • The approach assigns edge scores that can indicate relationship strength, but unlike trust-propagation methods that may use paths of arbitrary length, it bounds paths by κ.The section discusses trust relationships as one possible interpretation of edges in virtual communities.Source: §5.3 · pp. 21–22

6. Conclusions

The paper concludes that κ-path edge centrality can be computed on large social networks using bounded random walks in O(κm) time. It identifies community detection, visualization, tie-strength estimation, and parallel computation as future directions.

6. Conclusions

  • The κ-path edge centrality algorithm performs bounded-length random walks and has worst-case time complexity O(κm), with m denoting the number of edges.The conclusion reports experiments on different online social network datasets.Source: §6 · p. 22
  • The authors propose using the measure to detect communities in large networks and potentially support visualization of their hierarchical structure.They note that classic edge betweenness is currently impractical for this large-network task and describe their approach as a possible fit.Source: §6 · p. 22
  • Future work includes estimating the strength of ties between two actors, such as the degree of friendship between Facebook users..Source: §6 · p. 22
  • The authors identify parallel algorithms for κ-path edge centrality as a research opportunity.They point to existing parallel work on betweenness centrality as context.Source: §6 · p. 22

Appendix

The appendix establishes how ERW-KPath and WERW-KPath scores relate to the defined κ-path edge-centrality values. It expresses the index through probabilities of simple paths containing an edge and gives an exact ERW relation and bounds for the weighted version.

Appendix

  • Lκ(e) sums contributions from simple paths of lengths 1 through κ over all source nodes, with a path contributing only when it contains e.A contributing path adds its selection probability.Source: Appendix · p. 23
  • Each of ρ trials generates a simple path of at most κ edges, so an edge can be selected at most once per trial.The algorithm begins with a baseline edge score and adds an award when the edge is selected.Source: Appendix · p. 24
  • ω(e)=1/|E| + ρ/(|E||V|)Lκ(e) for ERW-KPath, relating its returned edge score exactly to the defined centrality index.Theorem 6.2 states this relation for each edge.Source: Appendix · p. 24
  • WERW-KPath’s weighted score is bounded in relation to Lκ(e) by suitable constants proportional to ρ/|E|.The proof uses weighted source-node and path-selection probabilities to derive bounds.Source: Appendix · pp. 24–26
Loading 1303.1747v1…