# How to Weight Edges with Number of Common Acquaintances

## Introduction : the concept of "structural embeddedness"

The concept of structural embeddedness refers to how a certain tie is embedded in the social structure. This is measured by "how many common acquaintances exist between the two nodes."

The degree of structural embeddedness can be used as strength of a tie, when it is not possible to directly observe the depth of the relationship between node pairs, such as attachment or number of interactions. The structural features of the network are convoluted as edge weights.

The research that dealt with this, classically, has the following papers. In this paper, it is revealed that the number of common acquaintances is more time stable than the likes and dislikes and the time spent.

This concept is derived from Granovetter's "social embeddedness" concept. This is a concept that covers the type of ties and social situations such as "family relations" and "marital relations", but structural embeddedness focuses on structural aspects, especially.

The problem is how to calculate the number of people in common. You can implement it by the double loop, but if you exploit of the properties of the adjacency matrix, you can reduce it into matrix calculation, so it is possible to calculate very fast.

For undirected graphs without loops, if you calculate the power of the adjacency matrix, each element of the matrix is equal to the number of n-paths between i and j . When n = 2, the number of n-paths is the same as the number of nodes to which node i and node j are connected in common.

## Implementation

library(igraph)
library(ggnetwork)
library(tidyverse)


### Generate a random graph and visualize it

set.seed(111)
network <- erdos.renyi.game(15,0.3)

original_layout <- layout.fruchterman.reingold(network)

gnet <- ggnetwork(network,layout = original_layout)
g <- ggplot(gnet,aes(x=x,y=y,xend=xend,yend=yend))
g <- g + geom_edges(size=0.5)
g <- g + geom_nodes(size=3)
g <- g + geom_nodelabel(aes(label = vertex.names))
g <- g + theme_blank()
g <- g + ggtitle("ORIGINAL NETWORK")
g


## The original adjacency matrix

adjmat <- as_adjacency_matrix(network)

15 x 15 sparse Matrix of class "dgCMatrix"

[1,] . . 1 . . . . . . 1 1 1 . . .
[2,] . . . . . . . . . . . . 1 1 1
[3,] 1 . . 1 1 . . . . 1 . 1 1 1 1
[4,] . . 1 . . . . . . . . . . 1 .
[5,] . . 1 . . . 1 . . . 1 . 1 . .
[6,] . . . . . . . 1 1 . . 1 1 . .
[7,] . . . . 1 . . 1 . . . . . . .
[8,] . . . . . 1 1 . 1 . . . . . .
[9,] . . . . . 1 . 1 . . 1 1 . 1 1
[10,] 1 . 1 . . . . . . . 1 . . 1 .
[11,] 1 . . . 1 . . . 1 1 . . . . 1
[12,] 1 . 1 . . 1 . . 1 . . . . . .
[13,] . 1 1 . 1 1 . . . . . . . . .
[14,] . 1 1 1 . . . . 1 1 . . . . .
[15,] . 1 1 . . . . . 1 . 1 . . . .

Next, let's square the adjacency matrix. To calculate matrix product in R, you can use %*% operator.

squared_adjmat <- adjmat %*% adjmat

15 x 15 sparse Matrix of class "dgCMatrix"

[1,] 4 . 2 1 2 1 . . 2 2 1 1 1 2 2
[2,] . 3 3 1 1 1 . . 2 1 1 . . . .
[3,] 2 3 8 1 1 2 1 . 3 2 4 1 1 2 .
[4,] 1 1 1 2 1 . . . 1 2 . 1 1 1 1
[5,] 2 1 1 1 4 1 . 1 1 2 . 1 1 1 2
[6,] 1 1 2 . 1 4 1 1 2 . 1 1 . 1 1
[7,] . . 1 . . 1 2 . 1 . 1 . 1 . .
[8,] . . . . 1 1 . 3 1 . 1 2 1 1 1
[9,] 2 2 3 1 1 2 1 1 6 2 1 1 1 . 1
[10,] 2 1 2 2 2 . . . 2 4 1 2 1 1 2
[11,] 1 1 4 . . 1 1 1 1 1 5 2 1 2 1
[12,] 1 . 1 1 1 1 . 2 1 2 2 4 2 2 2
[13,] 1 . 1 1 1 . 1 1 1 1 1 2 4 2 2
[14,] 2 . 2 1 1 1 . 1 . 1 2 2 2 5 3
[15,] 2 . . 1 2 1 . 1 1 2 1 2 2 3 4

The elements of resulting matrix equal to the number of 2-paths for each component between i and j. Of course, the diagonal is equal to the degree of each node.

Finally, to weight only edges where there was an edge originally, calculate the element product with the adjacency matrix and finally calculate the element sum with the adjacency matrix.

weighted_adjmat <- squared_adjmat * adjmat + adjmat

> weighted_adjmat
15 x 15 sparse Matrix of class "dgCMatrix"

[1,] . . 3 . . . . . . 3 2 2 . . .
[2,] . . . . . . . . . . . . 1 1 1
[3,] 3 . . 2 2 . . . . 3 . 2 2 3 1
[4,] . . 2 . . . . . . . . . . 2 .
[5,] . . 2 . . . 1 . . . 1 . 2 . .
[6,] . . . . . . . 2 3 . . 2 1 . .
[7,] . . . . 1 . . 1 . . . . . . .
[8,] . . . . . 2 1 . 2 . . . . . .
[9,] . . . . . 3 . 2 . . 2 2 . 1 2
[10,] 3 . 3 . . . . . . . 2 . . 2 .
[11,] 2 . . . 1 . . . 2 2 . . . . 2
[12,] 2 . 2 . . 2 . . 2 . . . . . .
[13,] . 1 2 . 2 1 . . . . . . . . .
[14,] . 1 3 2 . . . . 1 2 . . . . .
[15,] . 1 1 . . . . . 2 . 2 . . . .

Let's visualize the weighted adjacency matrix. After creating a network object in igraph, subtract 1 from the edge weight. Edges that do not have any common acquaintances will be displayed with a weight of 0.

weighted_network <- graph.adjacency(weighted_adjmat,
mode = "undirected",
diag = FALSE,
weighted = TRUE)
E(weighted_network)$weight <- E(weighted_network)$weight - 1

gnet <- ggnetwork(weighted_network,layout = original_layout)
g <- ggplot(gnet,aes(x=x,y=y,xend=xend,yend=yend))
g <- g + geom_edges(size=0.5)
g <- g + geom_nodelabel(aes(label=vertex.names))
g <- g + geom_edgelabel(aes(label=weight))
g <- g + theme_blank()
g <- g + ggtitle("WEIGHTED NETWORK")
g