Information Spreading and Evolution of Non-Homogeneous Networks

Abstract

Information spreading among nodes of directed random networks by means of the linear preferential attachment (PA) schemes and the well-known SPREAD algorithm is considered. The novelty of the paper is that schemes of the linear preferential attachment proposed in Wan et al. (2020) for the network evolution are also used here for the information spreading. The SPREAD algorithm proposed for undirected random graphs is adapted to directed graphs. Moreover, we deal with non-homogeneous directed networks consisting of nodes whose in- and out-degrees have different power law distributions that is realistic for practice and we find communities in a network that spread the information faster. We compare the minimum number of evolution steps $K^*$ required for the preferential attachment schemes and the well-known algorithm SPREAD to spread a message among a fixed number of nodes. The evolution of the network in time starts from a seed set of nodes. We study the impact of the seed network and parameters of the preferential attachment on $K^*$ for simulated graphs. Real temporal graphs are also investigated in the same way. The PA may be a better spreader than the SPREAD algorithm. This is valid for the sets of the PA parameters with dominating proportions of created new edges from existing nodes to newly appending ones or between the existing nodes only. It is shown both for simulated and real graphs that the communities with the smallest tail indices of the out-degrees and PageRanks may spread the message faster than other communities.