Find six degree separation in Actor-Actor Network

Question

I have tried to find the center node in an Actor-Actor network. When I said center node, I meant that the node which has the shortest paths to all other nodes in network.

For example:

df <- structure(list(Movie.Name = structure(c(1L, 1L, 1L, 1L, 2L, 2L, 
2L, 2L, 2L, 3L, 3L, 3L, 4L, 4L, 4L), .Label = c("A", "B", "C", 
"D"), class = "factor"), Actor.Name = structure(c(1L, 5L, 6L, 
7L, 8L, 5L, 9L, 1L, 10L, 11L, 8L, 12L, 2L, 3L, 4L), .Label = c("Actor1", 
"Actor10", "Actor11", "Actor12", "Actor2", "Actor3", "Actor4", 
"Actor5", "Actor6", "Actor7", "Actor8", "Actor9"), class = "factor")), .Names = c("Movie.Name", 
"Actor.Name"), class = "data.frame", row.names = c(NA, -15L))

From this bipartite network, I projected the actor-actor network and find shortest path for all nodes with this code:

library(igraph)
g_graph <- graph.data.frame(df,directed=FALSE)
V(g_graph)$type <- bipartite_mapping(g_graph)$type
# project only actor&actor network
projected_g <- bipartite_projection(g_graph, multiplicity = TRUE, which = TRUE)
# Get connected nodes in largest component
# get largest component
getmax = function(g) {
  V(g)$comp = clusters(g)$membership
  delete.vertices(g, V(g)[V(g)$comp!=which(clusters(g)$csize==max(clusters(g)$csize))])  
}
lc_projected_g <- getmax(projected_g)
# Turn weights into sample value!! 
E(lc_projected_g)$weight <- 1
# Find shortes path from one to all nodes
p_short <- shortest.paths(lc_projected_g)
p_df <-as.data.frame(rownames(p_short))
p_df$Total_path_length <- rowSums(p_short)
# Find eigenvector centrality!!!
projected_eig <- eigen_centrality(lc_projected_g)$vector

My questions are:

In igraph weight is considered as a cost or close relationship so it is right to convert weights into same value? Even though there are many edges between Actor01 and Actor02 , the length of path will be one!
After calculated the shortest path for all nodes, there are three nodes that have the same value. In this case eigenvector centrality is the right way to find center node?
When I projected the bipartite network, I lost edge names in Actor-Actor network. How can I assign them back?

I hope that my questions are clear and reasonable. Thanks in advance.

nJGL nJGL · Accepted Answer · 2019-01-18T08:45:59

The node with the shortest path to all other nodes would be the node with the lowest farness, or the highest closeness centrality calculated in igraph with closeness() See ?closeness() and Bavelas (1950) and the nice wiki-page for centrality measures.

Answers to the three subquestions below:

1) In igraph, weight is friction, not lubricant. See my recent answer to the same question here for more details

2) I think closeness-centrality sounds more like what you're looking for: "the lowest summed distance to all other nodes". In your case, both eigenvector-centrality (which has a more intricate and less intuitive formula I think) and closeness centrality leaves you with a tied winners. Compare:

eigen_centrality(lc_projected_g)$vector
closeness(lc_projected_g)

Deciding which is the right node if many winners have the same value is really a question of your own judgement. Since multiple scholars had Erdős-number 1, Paul Erdős used an alternative formula for the lowest Erdős-number with 1 over k co-published papers to award the lowest Erdős-number to the person with the most co-published papers (k) with him. My suspicion is that the reproductions of your kind of affiliation networks would produce structures with "tied winners" for the shortest path to all other nodes also in slightly larger graphs than yours. Perhaps you could re-think why you'd like the most central node of your re-projection to mean by going back to the original bi-partite structure of your graph?

3) You lost your edge-names because the reprojected edges are essentialy not the same edges at all. Be glad that they're gone. I can't reproduce any lost edge-names with your code, though. g_graph doesn't have names or labels set for E(g). E(lc_projected_g) lists nicely named edges since the vertices are nicely named. You could always re-build your own names like:

E(lc_projected_g)$label <- apply(ends(lc_projected_g, E(lc_projected_g)), 1, paste,collapse="--")

provided that your vertices are already correctly named. Your projection with bipartite_projection() should always bring verticy-names along, but not edge-names. In your code above, they do - at least for me. My code-line above sets the label (which shows up when plotting the graph) using paste() to glue the names of each edge's verticy-pair together by "--". Check out ends(lc_projected_g, E(lc_projected_g)). It should list named verticy-pairs as a matrix.

Many questions in one, but nicely working code-example. Good luck.

Find six degree separation in Actor-Actor Network

1 Answers