Temporal Networks [10/15]

Maira Saboia, Venkatesh Yerneni and Vinayak Karuppasamy -October 15, 2015

pic01
Social Evolution Network (matrix)

This lecture will be about examples of Temporal Networks. The first network mentioned here uses social evolution data set. The matrix depicted in the Figure 1 was drawn using this data set, which is about to a group of undergraduate students in a small student dormitory at the MIT Campus. Surveys were conducted at different times, almost at the end of every month. The data selected include locations (WiFi access points) and proximity data. Each matrix in the Figure 1 represents a survey on a certain relationship at a certain time. Each column is indexed by somebody who filed out the survey, and the rows correspond to the people asked about.

From the aforementioned matrix we can see that close friends is a subjective decision; socializing with means spending at least two hours per week and so forth. And since that time was the time of presidential election, we also asked about whether people discussed politics. This is a very typical kind of social network. If we look at those matrix it is possible to see clusters. If we look over time, we find out that, for example, some clusters began pretty small and they grow in size and so on and so forth.

pic02 pic03

Social Evolution Network (Graph) : Friendship Network (Left – 2008.12, Right – 2009.03) 

Figure 2 is a second view of this same network. Those are still the undergraduate students from freshman to senior, and there are also several graduate tutors. In this student dormitory there are four floors, and each floor is separated by a firewall in the middle into two parts, and there is passage in the firewall of the third floor. People on both sides of the firewall could communicate with people on other side.

Students organized in terms of the living sectors. The living sectors are represented with different colors. We can see that there are a lot of interactions between the green people and the yellow people. We also have numbers, which represent different schools years. We can see, for example, the freshman go together three months after the semester began. If we look at the network again, after another three months, although the freshman are still there they get mingled into other group of people in this undergraduate dormitory. There are also other changes.

Suppose that we can ideally ask a survey about the relationships every day. Suppose we have this ground truth, then the question that we can ask are: what is the mechanism for people to form friends and for people to dissolve their relationship? Whether or not we can interpolate the snapshots of the dynamic networks using an event trigger model. And whether or not the interpolation of the networks in between the observations grew with what, supposing that we have a ground truth.

Another question is, if we think about it in terms of KL divergence, how well are our estimations of the snapshots of the dynamic networks between our service? We can also ask what are the different graph rates or different weight that we will use? and what are the sufficient statistics that corresponds to the formation of this kind of network?

pic04

Product Space Network CA Hidalgo, B Klinger, A-L Barabasi, R Hausmann. “The Product Space Conditions the Development of Nations” Science (2007) 317: 482-487

Another network, which is also very interesting, is the Product Space Network. The origin of this network is the discussion about the rich people club. The idea is that imagine that we have a forest, and in this forest we have many trees, there are high branches and low branches in the trees, and we have monkeys. The idea is that there are monkeys on the high branches and there are monkeys at the low branches. But normally it is pretty hard for monkeys from low branches to climb up to the high branches. High branch monkeys do not want to go down to the low branches either.

In terms of the GDP (Gross Domestic Product) of different nations, and the richness of different nations, we have the same kind of problem. The idea is why some nations are richer than some other nations. This is because the monkeys of the high branches need to give a hand to the monkeys at the low branches to climb up.

We can observe that we have different industrial sectors and the different industrial sectors are related with one another in the sense that, for example, if I manufacture chips then I will have better access with to software engineering. For example, it takes longer for people to grow vegetables to be able to write code. The reason is that there is big gap between the people who grow vegetables to the people who write code.

It is possible to correlate different industrial sectors and then if a nation has import or export of both type of industry, then the distance is closer. If a country either import or export one kind of thing, or another kind of thing, but never both, then distance between those two is longer.

The red lines represent lines that are pretty close, and this not according to the geometric distance. The red lines are pretty close, and the blue lines are a little further and the yellow lines are even further.

For the countries who have already mastered the production of some products, then this country could very easily navigate from those products to the nearby products. But it will take longer time to navigate from those products that are further away.

The Coauthorship network represents a collaboration network. Each node in this graph represents a person, and the nodes are colored according to the person field of study. The chances of collaboration are represented by the distance between the nodes. On observing this graph, we see that people in the same area with similar colors, collaborate with each other. This can be seen in the graph that all nodes with the same color are clustered together, which makes complete sense that people working in the same field tend to collaborate on research ideas.coauthorship

Coauthorship Network, M. E. J. Newman. “Coauthorship networks and patterns of scientific collaboration”. PNAS 2004 101

However from a new observation of this graph can be seen that there are chances for collaboration between nodes of different colours depending on their distance from each other. For example, we can see from the graph that nodes in statistical physics are closer to nodes in ecology, and ecology nodes are also close to nodes in nodes in agent based modeling. This can be true as people in ecology also do multi-agent modeling. This kind of modelling can give interesting results like, what will the next paper be about? Or what kind of collaborators can we have for a particular paper? These insights can be used to maximize our benefits in terms of game theory and modern perspective.

One of the many things that such networks are used for is trying to predict their evolution overtime, by looking at it snapshot by snapshot. Interpolating the snapshots will give us a prediction about the growth of the network and also explain the parameters of their growth. These networks also give a lot of information about their asymptotic properties, like what would be the properties of the network if it were infinitely large. An interesting property of this network in this regard is that, while keeping the density of the network constant if we keep on increasing the number of edges, we will get a connected network, i.e. the network will consist of only one component, which is a surprising property of this network.

There are many other properties, which is why these networks are important. Reasoning about these properties give useful insights. If we let the size of the network to go to infinity, meaning we are dealing with a network of internet, that is basically one component. Another network of a similar type is the small world network. This network tells us that the degrees of separation between any two people in the world is 6, i.e. any two people in the world are connected with atmost 6 people in between. We have a regular connected network which is like an abstraction. That for example that people are connected with one another through their physical distances. A person has a higher probability of being connected to then people within, for example, 10 miles away from himself, or in a social structure a person is more likely to be connected with another person working in the same organization.

This kind of regularly connected network, or regular graphs of any dimension are just abstractions of such ideas. The way to form this idea is to randomly rewire the edges. Take all edges from one person to another person in a grid. And then randomly rewire this into another node randomly sampled in a whole network. In this manner, given any two nodes, we will use those randomly rewired edges to go very quickly from one place to another, and use the regular edges, the green edges to navigate at the nearby locations, and that is one way to quickly get from one person to another person. The average distance between any two people grows as the logarithm of network size. It is the size of our social network.

The interesting thing is, those kinds of things and those kinds of properties and other properties that where mentioned can be either found out analytically if there is an analytical solution, or can be found through simulation. What we have here is this nice property about average path length, and also in this kind of network we have very large cluster coefficient. Meaning that if A knows B, and B knows C, then A knows C. In this world we have the nodes of forming different clusters.

erdos-renyiErdős–Rényi model

Watts-Strogatz1 Watts-Strogatz2

Watts-Strogatz model

Barabasi-AlbertBarabasi-Albert model model

What we will talk next is about this “Game Theory” perspective of a dynamic random network. We have a group of people and each person has certain properties, which can be considered as their resources. They might choose to be connected to another person or not connect to another person, or dissolve a previous edge. For each connection there is a cost to maintain this connection. So for each connection there will be a gain, the gain comes from sharing resources and sharing information; there will also be a cost, the cost comes from maintaining the edge. Each person in this network can only know the other people around. The idea is how can different people dynamically choose to connect to other people or not connect to other people over time, and whether or not there will be an equilibrium in the end.

Players, Networks, Chains and Components

What we have in this type of network is that we’ll have a set of players which are the nodes, and also we’ll have a set of networks and each network is connected to each other through a chain. This is the formulation of this kind of network:

  • Let $ N=\{1,…,n\} $ be a set of players
  •  Let $\{g:g\subset g^N\}$ be a set of networks, also called graphs, where $g^N=\{ij:i,j \in N,i \neq j\}$ is the complete network and ij is a link
  • Let$ N(g)={i:\exists j, s.t.\ ij \in g}$ be players involved in at least one link, $n(g)$ be the cardinality of $N(g)$
  •  A chain $i_1,i_2,…,in$ in $g$ connecting $i_1$ and in if ${i_1,i_2,…,i_n}\subseteq N(g)$ and ${i_1i_2,i_2i_3,…,i_{n-1}i_n}\subseteq g$
  • A nonempty network $g’$ is a component of $g$ if
    $i \in N(g’)$ and $j \in N(g’) \Rightarrow a$ connecting $i$ and $j$, and
    $i\in N(g’)$ and $j\in N(g)$ and $ij\in g \Rightarrow

Ref: Matthew O. Jackson (2003), “A Survey of Models of Network formation: Stability and Efficiency”, Chapter 1 in “Group Formation in Economics: Networks, Clubs, and Coalitions”, edited by Gabrielle Demange and Myrna Wooders, University Press: Cambridge in 2005.

Value, Efficiency and Allocation Rules

The next thing we will design in playing a network game is defining a value of this network, which is a function that maps a graph into a real number.

  • The value of a network $v:{g:g\subseteq g^N}\rightarrow \mathbb{R} $ represents the total utility or production of the network.

We say that network is strongly efficient if it has the maximum utility function than any other networks

  • A network $g\subseteq g^N$ is strongly efficient if $v(g) \geq v(g’)$ for all $g’ \subseteq g^N$
  • The allocation rule $Y:{g:g \subseteq g^N}\times V\rightarrow \mathbb{R}^N$ describes how the value of the network is distributed to individual players.

We have overall utility of this whole system, and we have different configurations which are in terms of whether people choose to connect or not. And we have allocation rule which maps a graph. So we have a graph and we also have a set of vertices and what we get is the utilities of the individual players.

Defining Network Games

The network game involves people adding a link or deleting a link. After individuals add a link or delete a link, the overall utility of this system will change, and the utility of the individuals will also change. The individuals tend to stochastically or deterministically operate the edges that they can manipulate in order to maximize their own utilities.

The idea that the researchers care about the most is whether the network is stable in terms of whether it will be able to form a strong efficient network. As the players in this network add edges or remove edges, we will form a sequence of networks and each network differs from the next network by just one edge, in this sense they’re adjacent. We can think of this as a Markov of chain.

  • Networks $g$ and $g’$ are adjacent if $g’=g+ij$ or $g’=g-ij$, where
    $g+ij$ be the network obtained by adding link $ij$ to network $g: g+ij=g\{ij\}$
    $g-ij$ be the network obtained by adding link $ij$ to network $g: g+ij=g\{ij\}$
  • Network $g$ is pairwise stable with respect to $v$ and $Y$ if
    $\forall ij \in g,Yi(g,v)\geq Yi(g-ij,v)$ and $Yj(g,v)\geq Yj(g-ij,v)$
    (no player could benefit by severing an existing link) and
    $\forall ij \notin g,Yi(g,v)<Yi(g+ij,v) \Rightarrow Yj(g,v)>Yj(g+ij,v)
    $ (no two players would benefit by forming a new link)
  • A sequence of adjacent networks $g1=g,g2,…,gK=g’$ is an improving path from $g$ to $g’$ if for any $k$

$gk+1=gk-ij$ for some $ij$ and $Yi(gk-ij)>Yi(gk)$,(one link is deleted and at least one involved player strictly benefits from deletion) or 

$gk+1=gk+ij$ for some $ij$ and $Yi(gk+ij)>Yi(gk)$ and $Yj(gk+ij)\geq Yj(gk)$(one link is added and one involved player strictly benefit and the other doesn’t lose)

  • A set of network $C$ is a cycle if there exists an improving path from any $g\in C$ to any $g’\in C$

$C$ is a maximal cycle if it is not a proper subset of a cycle

$C$ is a closed cycle if no network $g\in C$ leads to an improved network not in $C$.

The question is whether or not they will reach one specific absorbing state, meaning that at that state nothing will change. In other words, they will end up with some kind of equilibrium in the sense that the statistics will forget the previous configuration a long time ago and it is something that has a detailed balance. Those are the two different considerations that we have.

Similar to what we have coped with in a Markov chain we might end up with a cycle in a sense that we end up with some periodic Markov chain, we go from A to B from B to C and from C to A. Those are the different configurations that we have in terms of network game.
One example of this network game (Trading Game) looks like following:

tradingGameTrading Game

We have four players, each player can have two goods $(0,1)$ or $(1,0)$ with probability is $1/2$. The utility of each player is $U(x,y)=x*y$, for x and y amount of different goods (expected utility per player is $1/8$, $1/6$ and $3/16$ for components $1, 2$ and $3$ players). The players will tend to either form an edge or dissolve an edge in order to maximize the utilities of themselves. Trade can only happen along the network and the cost of a link is $5/96$ per player.

We can play this game and we will find out that this network form a cycle, the players will repeatedly try to optimize the utility function, but in the end the greedy choice of the players will just bring the network dynamics in a circular fashion. So this is one example of the network game.

Another example of the network game is the Co-author network. In this network each player $i$ has $n_i$ project. Suppose that each player spends $1/n_i$ time on each project equally. Each player can collaborate with another player on exactly one project. It depends on how the player choose to build an edge or to dissolve an edge. When one player has collaboration with another player there is a synergy (utility of collaboration) which is expressed in terms of $u_i(g)=\sum_{j:ij\in g} 1/n_i + 1/n_{j}+1/n_{i}n_j$. The idea of this network is: what is the best way for players to choose the number of projects and to choose the connections of this network in order to maximized the utility or the productivity of different users? One thing that we know is that for any type of network game, either the game will end up with one absorbing state or will end up with a cycle of many absorbing state.

Pairwise Stable Network vs. Closed Cycle of Networks

Claim: for any $v$ and $Y$ there exists at least one pairwise stable network or closed cycle of networks.
Proof:

  • Starting network g
  • Either leads to a pairwise stable network or
  • Or leads to a cycle C.
  • We can expand C into a maximal cycle,
  • Which is closed cycle if no pairwise stable network exists.

This one says that for any network valuation function, $v$ (the utility of this network), there exists at least one pairwise stable network. Which is just one state, or a closed circle of networks. Players in the network continues to add an edge or remove an edge, and then form a cycle.

The idea to show this is actually pretty simple. It starts from a random network and then a player goes one step. Either this state is absorbing state, meaning that nothing will change or this specific network is not absorbing state. So if it not absorbing state we’ll go to another network in this graph. Since there is only a finite number of network configurations in this plot, we will end up with going back to some state. Either the first state or some state in the middle. If we go to some state in the middle, we ultimately get a cycle from the different types of configurations. This is the prove of this one.

Temporal Networks [10/15]

Leave a Reply