A model for network evolution.

 

GAIL GILBOA-FREEDMAN

TEL AVIV UNIVERSITY, ISRAEL

 

We consider a novel approach to random network evolution. In our model, N individuals move between locations or states. Some of these states are meeting states and a meeting there can add a link to the network if some additional requirements are satisfied. Formally, each individual is represented by a Markov chain. We assume N identical Markov chains that independently move between a common set of states. The time a chain spends at a given state is exponential with a known parameter. There are two types of states, L and M. If at any given time two chains are both in the same M-state, these chains meet. As a first step, we consider 2-state Markov chains with states L and M. We investigate the evolution of such networks and its characteristics (such as the clustering coefficient or the diameter) under several models. For example, • one of the chains is a leader and a link is added when a non-leader chain meets the leader; • as above but when a chain meets a leader it also become a leader (spreading a rumor); • a chain is matched to the first chain it meets; • there are several leaders and a non-leader chain becomes a follower of the first leader that it meets.