Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Suggestion: closeness vitality #129

Open
briatte opened this issue Oct 31, 2015 · 1 comment
Open

Suggestion: closeness vitality #129

briatte opened this issue Oct 31, 2015 · 1 comment
Labels
wishlist Feature request that has not been chosen for implementation yet; vote or comment to prioritize it!
Milestone

Comments

@briatte
Copy link

briatte commented Oct 31, 2015

Closeness vitality is a measure proposed in Brandes and Erlebach (2005), Section 3.6.2 (see screenshot below). It has been implemented in Python, in networkx.

The same function requires only a few lines of code with igraph:

closeness_vitality <- function(g) {
  a <- sum(igraph::distances(g))
  v <- sapply(1:igraph::vcount(g), function(v) {
    d <- igraph::distances(igraph::delete_vertices(g, v))
    a - sum(d[ !is.infinite(d) ])
  })
  names(v) <- V(g)$name
  v
}

(Ignoring infinite values in the distance matrix is only one among several options. It is the only one available through networkx, but the igraph implementation could be made to support additional options.)

As with my disparity filter submission, just let me know if you are interested, and I'll submit a proper PR.


Related: the closeness vitality of vertex x in graph g compares the Wiener index of g to the Wiener index of that same graph after vertex x has been removed. The Wiener index (which networkx seems to have misspelt as 'Weiner') would be trivial to implement in igraph:

wiener_index <- function(g) { sum(distances(g)) }

Another strategy is to compare average path lengths instead of Wiener indexes, which is sometimes called a 'vulnerability' measure:

vulnerability <- function(g) {
  d <- mean_distance(g)
  v <- sapply(1:vcount(g), function(v) {
    g2 <- delete_vertices(g, v)
    if (all(degree(g2) > 0)) { mean_distance(g2) - d } else { NA }
  })
  names(v) <- V(g)$name
  v
}

(The function returns NA if the vertex for which vulnerability is being computed is a cut-vertex or a bridge.)


@szhorvat
Copy link
Member

@briatte Can you help answer the two questions I wrote in igraph/python-igraph#144 ?

@ntamas ntamas added the wishlist Feature request that has not been chosen for implementation yet; vote or comment to prioritize it! label Oct 29, 2022
@krlmlr krlmlr added this to the future milestone Feb 20, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
wishlist Feature request that has not been chosen for implementation yet; vote or comment to prioritize it!
Projects
None yet
Development

No branches or pull requests

4 participants