Multirelational Graph

A multirelational graph is a graph where there are multiple types of edges. For example, in a social network, there could be edges for friendships, likes, follows, etc. This then also most often leads to a multigraph, which is a graph where there can be multiple edges between two vertices.

An example of a multigraph could be a road network where each edge represents a road and the vertices represent cities.

As an example of a multirelational graph, we can expand on the graph from above and add edges for other types of transport like trains.

Multiplex Graphs

A multireletional graph can also be split into layers of a multiplex graph. A multiplex graph is a graph where there are multiple layers of different edges but the same vertices.

A multirelational graph split into a multiplex graph.

Signed Graphs

A signed graph is a graph in which each edge has a positive or negative sign. They can be used to represent a relationship between two vertices. Because there are two possible edges between two vertices, a positive and a negative one, it means that a signed graph is a multirelational graph.

For example, a positive sign could mean that two people are allies and a negative sign could mean that they are enemies.

Triads and Balance Theory

Triads are a set of three vertices in a signed graph where each pair of vertices is connected by an edge, i.e forming a triangle. Triads are important in social network analysis as they can be used to determine the stability of a social network.

The balance theory states that a social network is balanced if all triads within that network are balanced. For a triad to be balanced, the number of negative edges must be even (0 being even). This leads to the following four possible triads:

balancedTriads

The first and last one are the simplest as they are either all positive or all negative. The idea of the second one is that it is balanced because "the enemy of my enemy is my friend". The third one is a common scenario that leads to issues in social networks. For example, if Alice and Eve are allies and Bob and Eve are alies but Alice and Bob are enemies, then this leads to issues in the social network if Eve wants to introduce Alice and Bob to each other.

Balanced Signed Graphs

From the above, we can see that a signed graph is balanced if all triads are balanced. Where a triade could also be defined as a cycle of length 3, $C_3$ .

N-Mode Networks

An n-mode network is a graph where there are multiple types of vertices and the edges can only connect vertices of different types. So in other words the graphs vertices can be split into $n$ disjoint sets and the edges can only connect vertices from different sets. A normal graph is a 1-mode network as there is only one type of vertex. A 2-mode network is a graph where there are two types of vertices and the edges can only connect vertices of different types.

For example, if we have a graph containing people and movies and the edges represent whether a person has watched a movie or not.

Bipartite Graphs

A graph $G$ is bipartite if its vertices can be split into two disjoint sets $V_1$ and $V_2$ such that every edge in $G$ connects a vertex in $V_1$ to a vertex in $V_2$ . So there are no edges between vertices in the same set!

This makes a 2-mode network a bipartite graph.

Bipartite Network Projections

The idea of a bipartite network projection is to project a bipartite graph to a "normal" graph i.e. 1-mode network. This can be done in a few ways.

Simple Projection

In the simple bipartite network projection, we project the bipartite graph to a 1-mode network by connecting two vertices if they have a common neighbor of the type to be removed in the bipartite graph.

For example, if we have a bipartite graph with people and events and the edges represent whether a person has attended an event or not. We can then project this bipartite graph to a 1-mode network where the vertices are people, and they are connected if they have attended the same event.

By doing this we can quickly find people that have been to the same events and might have similar interests. So if we have the below graph:

and perform a simple projection we get the following graph:

Weighted Projection

The problem with the simple projection is that it does not take into account how many edges two vertices have in common. For example, if two people have been to the same event 10 times, they will be connected the same way as two people that have only been to the same event once. To solve this, we can use a weighted projection.

In a weighted projection, we connect two vertices if they have a common neighbor of the second type (the one to be removed), just like in the simple projection, but the weight of the edge is the number of common neighbors. More formally:

w_{ab} = \sum_{k \in V_2} d_k^a d_k^b

Where $V_2$ is the set that contains the vertices of the second type, i.e. the one that will be projected away (in the example above, the events).
And where $d_k^a$ is 1 if $a$ and $k$ are connected and 0 otherwise and $d_k^b$ is 1 if $b$ and $k$ are connected.

The weighted projection could then also be normalized by dividing each weight by the maximum weight of the graph. This would then give us a value between 0 and 1.

We can clearly see that only Michael, Urs and Karen are the only ones that have been to the same event more than once (highlighted in red).

Newmann-weighted Projection

This projection is also sometimes called "collaboration weighted projection" (no idea why).

The idea of this projection is to further build up on the weighted projection by also taking into account the degree of the common neighbor, i.e. the number of edges connected to the common neighbor. To take this into account we can use the following formula to calculate the weight of the edge between two vertices $a$ and $b$ :

w_{ab} = \sum_{k \in V_2} \frac{d_k^a d_k^b}{\text{deg}(k) - 1}

Where $V_2$ is the set that contains the vertices of the second type, i.e. the one that will be projected away (in the example above, the events).
And where $d_k^a$ is 1 if $a$ and $k$ are connected and 0 otherwise and $d_k^b$ is 1 if $b$ and $k$ are connected.

This projection can be valuable if we imagine the following scenario:

We have a graph of people and events. We have an event like a concert where 5000 people attended, a birthday party where 15 people attended and an Open day at a university where 100 people attended. We can assume that if two people the party and the open day, they are more likely to have similar interests than if they both attended the concert, or we could simply state that it is more likely that they came in contact with each other at the party or open day than at the concert.

So if we project the same graph as above, we get the following graph:

The calculations are a bit more complicated than for the weighted projection, but nothing to complex:

\begin{align*} \text{Alice to Bob} &= \frac{1 \cdot 1}{2-1} + \frac{0 \cdot 1}{7-1} + \frac{0 \cdot 0}{4-1} = 1 \\ \text{Karen to John} &= \frac{0 \cdot 0}{2-1} + \frac{1 \cdot 0}{7-1} + \frac{1 \cdot 1}{4-1} = 0.33 \\ \text{etc...} \end{align*}

Overlap Weighted Projection

The overlap weighted projection is similar to the weighted projection, but instead of using the number of common neighbors, it uses jaccard similarity. So the weight of the edge between two vertices $a$ and $b$ is:

w_{ab} = \frac{N(a) \cap N(b)}{N(a) \cup N(b)}

General Definition Storing Graphs