Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

New Feature: Laplacian Centrality

Aperta
  • Qualcosa non va?
#290 1 commento 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Da chiarire
Stato di attività
Ferma
Stack tecnologico
julia, python
Ambito
analytics

Direzione di ricerca

Inizia con l’articolo di Qi et al. del 2012 e con l’implementazione collegata della centralità laplaciana di NetworkX, quindi esamina l’API di centralità esistente di Graphs.jl e la copertura dei test per i grafi pesati. Il lavoro sarà considerato completato quando saranno disponibili un design di implementazione concordato e test che coprano la misura di centralità laplaciana proposta sui tipi di grafo pertinenti.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

enhancement

Hello there,

I am opening this issue to discuss the possibility of implementing a new centrality measure called Laplacian Centrality. I found it very interesting and would have liked to know if it would have its place in the Graphs.jl project.

Description

This metric is presented by (Qi et al. 2012) for having two major benefits over classic centrality measures (e.g. degree, betweenness):

  1. It is naturally suited for weighted graphs.
  2. It resorts to an intermediate between global (like betweenness centrality) and local (like degree centrality) scope to characterize a vertex.

It is based on the Laplacian Energy of a graph $G$ measured by:

$$E(G) = \sum_{i=1}^{n} \lambda_i^2$$

with $\lambda_i$ the $i^{th}$ eigenvalue of $G$.

The formula for the centrality of a given vertex is given by the drop of energy when removing this vertex from the graph:

$$C_L(v_i, G) = \frac{E_L(G) - E_L(G_i)}{E_L(G)}$$

with $G_i$ the graph obtained from removing vertex $v_i$ from G.

Implementation

Although not providing any pseudo code, (Qi et al. 2012) describes a way to compute this measure efficiently, with a complexity of $O(n\Delta^2)$ with $\Delta$ being the largest degree in the graph at hand.

The formula goes like this:

$$E_L(G) - E_L(G_i) = 2.NW^E_2(v_i) + 2.NW^M_2(v_i) + 4.NW^C_2(v_i)$$

with $NW^E_2(v_i)$ the number of 2-walks ending or starting with $v_i$, $NW^M_2(v_i)$ the number of 2-walks having $v_i$ as middle vertex and $NW^C_2(v_i)$ the number of closed 2-walks including $v_i$.

Each of them can be described as sums and multiplications of edge weights.

NetworkX implementation

A current implementation of that algorithm exists in Python's NetworkX package. However, it recomputes eigenvalues for each subgraph, leading to a simpler but potentially suboptimal algorithm according to (Qi et al. 2012).

Question about unit testing

I seemed to realize that the Graphs.jl library did not test its centrality measures using weighted graphs the likes of SimpleWeightedGraphs. If this algorithm is implemented, would it be suitable to test for these graphs here as well? (the only case of weighted graph test I found was for betweenness_centrality using an external distance matrix).

Would the implementation of such a metric be of interest to the project?

Thanks for reading me!

Lingua principale
Julia
Stelle
539
Fork
130
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di JuliaGraphs/Graphs.jl

Tutte le issue di JuliaGraphs/Graphs.jl

Issue simili

Altre issue su Julia

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.