Weighted, Directed, Multilayer Diffusion Networks
So far, we have studied diffusion in fairly simple graphs. In these graphs, all edges are bidirectional and all edges represent the exact same type of connection or interaction between nodes. However, real life is much more complex and we need to develop more advanced machinery to study it. We will add complexity to our graphs in steps and then explain how diffusion acts on the more complicated graphs.
First, we can make our edges oriented. So the edge (u,v) is not the same as the edge (v,u). In some cases we will want u to send information to v and v to send information to u. In this case we will have both edges (u,v) and (v,u). Directed graphs often make more sense in terms of simulating real life situation than undirected graphs. For instance, if we are considering a social media network like Twitter, someone like the president is able to send information to lots of people as they have lots of followers. However, those followers cannot send information to the president. So we see a natural directed flow of information here.
Next, we want to add weights to the edges. So we now consider a function w: V x V -> R where R is the real numbers. Depending on the situation, we may want the weight function to be strictly non-negative, but for now we will not impose that restriction. So each edge (u,v) has an associated weight. Note that since we are working in a directed graph now, the weigh of (u,v) may be very different from the weight of (v,u). Let’s again consider the example of the social media network of Twitter and the president. Let person u be a follower of the president which we will represent by node p. Then let m be the node corresponding to a mayor of a neighboring town of person u that they are following. Then it makes sense that (p,u) is weighted much higher than (m,u). By adding weight, we can add power to a network. Alternatively, if we are looking specifically at network cascades, we may want the weight of an edge to approximate the probability that information is spread across that edge. So if person u adopts behavior A they may not inform their neighbor v of this so the weight corresponds to how likely they are to pass on the information.
The final addition we will make to the graph is by far the trickiest. Let us just start with N nodes. Let us think of these nodes as all sitting on a plane. The we want to make K copies of this. So we have K parallel planes each with N nodes on them. Now on each plane we add edges to form a directed, weighted graph on each plane. The reason we have these copies of the nodes is so that on each plane, we want the edges contained in the plane to mean different things. So for instance if we are considering a larger social media network we may take edges on one plane to be interactions through Twitter and on another plane edges may be interactions through Facebook. This makes the spread of information significantly more interesting. For instance, on Twitter, we have strictly directed edges as we have discussed (you are following the president but the president is not following you). Alternatively, on Facebook are edges are bidirectional since it is a friend network. So information will spread very differently across these two networks even though they correspond to the same people. Now consider person u spreads information to person v via plane i then v spreads information to person w via plane j. So information moves through the planes as well. This copying and parallel planes formation of a multilayered network is just one way to form a multilayered network; there are many other ways.
Currently, it is an interesting problem to model how cascades occur in these multilayered networks. Researchers have implemented many different ways to try to understand how these cascades occur with varying number of dimensions (number of planes) as well as changes in weights and edge connections. The conclusion that we have been working with for our more simple graphs do not always hold when these other variables are introduced. However, we can try to restrict certain aspects of these multilayered networks (say for instance looking at one plane at a time) and hope to see the same results we’ve had before and extrapolate them to these larger dimensions. Right now, as researchers use computers to work through these complicated networks to study diffusion and cascades, they must work to optimize how the computer handles the network. Better optimization will lead to more results on more complicated networks.
https://arxiv.org/pdf/2111.06235.pdf