Imagine a network in which nodes are connected by links representing different kinds of connections.

Example: Alice and Bob transact financially with each other, so they are connected by a "transaction link". Bob and Carol both belong to the same sports club, so they are connected by a "club link".

From a graph theoretic perspective with Alice, Bob, and Carol as nodes, edge colouring would seem to be one way of thinking about this, yet my very shallow research seems to indicate that edge colouring is primarily concerned with edge colouring theorems and algorithms. I am more interested in using these different kinds of edges to analyse the graph in the sense of network science.

What is the correct framework or body of literature for thinking about the single network which includes Alice, Bob, and Carol, while preserving the different types of connections that they have?

  • 1
    $\begingroup$ There may not be a "correct framework". You can always put appropriate labels on the edges and decide when your analysis must take those labels into account. The separate networks may be very weakly interacting - you could specify that. You could even allow some edges to carry multiple labels. Of course if there's no interaction you just have a set of separate graphs that happen to share some vertices. $\endgroup$ – Ethan Bolker Mar 12 '18 at 20:17
  • $\begingroup$ Thanks Ethan. As an example, one thing one may wish to do is specify the strength of those interactions in terms of a probability, conditioned on things such as betweenness centrality. In that context, is "edge labelling" or "link labelling" a useful line of enquiry to follow? $\endgroup$ – Christopher Mar 12 '18 at 20:35
  • $\begingroup$ Probably. You can use the probabilities to combine the results of things like centrality computed separately for the labelled networks. I think your best strategy is to let the label-and-probability structure emerge from your ongoing research. Keep it flexible. $\endgroup$ – Ethan Bolker Mar 12 '18 at 20:54

Sounds like what you are describing is a multilayer graph. For example think about a fixed set of individuals $V = \{A, B, C\}$. They may have different connections personally and professionally e.g. A and B are personal friends but not professionally. So, there are two sets of edges $E_{per}$ and $E_{pro}$ denoting their personal and professional relationships. Hence, we have two graphs $G_{per} = (V, E_{per})$ and $G_{pro} = (V, E_{pro})$. In abstract terms, no we have a tensor instead of an adjacency matrix.

For more information on such models and their analysis, have a look at:

--Multilayer networks (M Kivelä, A Arenas, M Barthelemy et al)

--Mathematical formulation of multilayer networks (M De Domenico, A Solé-Ribalta, E Cozzo, M Kivelä)

Hope this helps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.