R: network analysis - manipulating adjacency matrix to obtain a "common links" matrix

Question

I am doing some network analysis using the igraph R package.

I have to manipulate a directed, weighted adjacency matrix (extracted from an igraph object with the function _as_adjacency_matrix(...)_, in order to obtain a different matrix that takes into account the number and the weight of the incoming links that two nodes share with each other.

Assume 4 nodes: node A is connected to node C, node B is connected to A, node C is connected to node A and B, node D connected to A with all links to be directed.

In this setup, A and B shares the inward link from C but no other node share any incoming link.

Thus, I would like to create a routine able to create a directed weighted adjacency list from the original one, where each entry [i,j] represents the sum of the value of incoming edge that node i,j share with each other.

The result has to be a logical matrix (only true/false values) that is symmetrical, at front of a resulting "common link" adjacency matrix that is instead directed.

Back to the example I made, only the entries [A,B] and [B,A] should have a non-zero value, equal to the value of inward edges from shared connected nodes ([A,B] should contain the [C -> A] value, while [B,A] should instead contain the [C -> B] value).

Any suggestion about it would be extremely appreciated

Please proved a minimal reproducible example: stackoverflow.com/questions/5963269/… so that we can see a sample of the data and what you expect your output to look like. As well as any attempts you have made (SO is not a code writing service) — emilliman5
Your post seems to conflict with itself: You say you the result has to be a logical matrix but then you say [A,B] and [B,A] should have a non-zero value, equal to the value of inward edges from shared connected nodes ([A,B] should contain the [C -> A] value, while [B,A] should instead contain the [C -> B] value) if two nodes had shared more than 1 incoming node what should be reported. Lastly, if this is to be a directed weighted adjacency matrix it may not be symmetric — emilliman5
Dear @emilliman5, maybe I have not been very clear: what I meant to say is that the logical matrix (the 0-1 translation of the directed weighted adjacency matrix that I would like to create) should be symmetrical, not the adjacency matrix itself. As an example, let's suppose [C-->A] = 20, and [C-->B] = 15, the directed matrix would be non symmetrical, but both should result in a value 1 in the logical matrix. I will provide a reproducible example as soon as I can, hoping you will be wishing to help ;-) — Filippo Santi

nJGL nJGL · Accepted Answer · 2018-03-18T14:43:39

Interesting but slightly vaguely defined problem. I had some trouble understanding your desired output, but I think I got it. I left code from my first try below. The example data you provided I call g.

Either way I think you can have a lot to go on from this code example. I'm very much open for a smarter way to do this without loops for speed, but this is instead the most pedagogical code I could come up with being as I wasn't sure about the desired output.

If I understand your problem correctly, what you asked for will be outputted in the list ul where ul[[x]][[3]] contains the E() of a graph where edges go from the node i (ul[[x]][[1]]) to each of the nodes from which i and j share incoming links in the graph g.

library(igraph)

# Assume 4 nodes:
# - node A is connected to node C,
# - node B is connected to A,
# - node C is connected to node A and B,
# - node D connected to A
m <- matrix(ncol=4,c(0,0,1,0,
            1,0,0,0,
            1,1,0,0,
            1,0,0,0), byrow=T)
colnames(m) <- rownames(m) <-  c("A","B","C","D")

# Uncomment this stuff to use random network instead
# g <- erdos.renyi.game(n=12, 16, type="gnm", directed=TRUE, loops=FALSE)
# m <- as.matrix(as_adjacency_matrix(g))

# Check that the data is ok
graph_from_adjacency_matrix(m, mode="directed")
g <- graph_from_adjacency_matrix(m, mode="directed")

# Directed weighted adjacency list from the original one, where
# each entry [i,j] represents the sum of the value of incoming
# edge that node i,j share with each other.


# I first missunderstood your question and wrote this output

# This output will be an edgelist containing node-pairs i and j and
# the strength related to the number of other nodes whith which they
# share incoming links.
el <- matrix(ncol=3, nrow=0)
colnames(el) <- c("i","j","strength")

# I then reread your question and made this output containing a list
# wehre every node-pair which share incoming links from the same nodes
# contain the E()-object of igraph-edges from i to each of the nodes
# from which both i and j recieve incoming links in the graph g.
ul <- list()

# Use the empty graph like g to build edgelists
temp.g <- g %>% delete_edges(E(g)) # an empty graph

for(i in V(g)){
    for(j in V(g)){
        # Each node pair is i j for every node in g
        if(i == j){next}


        # Neighborhod() lists linked nodes, in this case at the distance
        # of exactly 1 (mindist and order) for node x using the "in"-coming
        # links:
        in.to.i <- neighborhood(g, order=1, nodes=i, mode="in", mindist=1)
        in.to.j <- neighborhood(g, order=1, nodes=j, mode="in", mindist=1)

        # These are the nodes which all link to both i and j
        shared.incoming <- intersect(in.to.i[[1]], in.to.j[[1]])

        # Make a new graph (gg) with links from each node FROM which i and j both
        # share incoming ties in g TO  i.
        # In the edgelist ul, each row can be read like:
        # In graph g, "i" has "edges" incoming ties in common with "j"
        gg <- temp.g %>% add_edges(unlist(lapply(shared.incoming, function(x) c(x,i)) ))

        # E(gg) is what you want. Add it to the output-list
        ul[[length(ul)+1]] <- list(i, j, as_edgelist(gg, names=T))

        # how many nodes link to both i and j?
        el <- rbind(el,c("i"=i, "j"=j, "edges"=length(shared.incoming) ) )
    }
}

# The whole list of el contains all possible pairs
el

# Strip entries in the edgelist where a pair of nodes don't share any
# in-linking nodes at all
el <- el[el[,'strength'] != 0,  ]

# Since nodes that share in-linking nodes are ALWAYS structually equivilent
# in that they both share in-links from the same other nodes, there is never
# any idea to have this edge-list directed.
# Make the edge-list one-directed by deleting duplicate pairs
el <- el[el[,'i'] < el[,'j'],  ]

# In graph g, these node-pairs share the number of [strength] incoming links
# from the same other nodes.
(el)


# The whole list of ul contains all possible pairs
ul

# You only wanted the pairs which actually contained any shared incoming nodes
keep.from.ul <- unlist(lapply(ul, function(x) ifelse( nrow(x[[3]]) > 0, TRUE, FALSE) ))
ul <- ul[keep.from.ul]

R: network analysis - manipulating adjacency matrix to obtain a "common links" matrix

1 Answers