Information Spreading in Non-homogeneous Evolving Networks

Maksim Ryzhov, Natalia Markovich
The paper is devoted to finding of leader nodes in evolving directed random networks with regard to the information spreading. We consider non-homogeneous networks consisting of several weakly connected subgraphs having different distributions of node in- and out-degrees. This is a plausible situation for real complex networks. The evolution of the network in time starting from a seed set of nodes is provided by linear preferential attachment schemes. We compare the spreading rate of nodes which share their messages with other nodes when they belong to different subgraphs of the non-homogeneous network. It is found that the nodes of the subgraph with the most heavy tailed out-degree distribution may spread their messages faster. We compared the spreading capacity of the linear preferential attachment used also for the graph evolution with a well-known SPREAD algorithm and found that the latter can disseminate the information faster.