Leader Election in Communities for Information Spreading

Natalia Markovich, Maksim Ryzhov
The paper is devoted to the information spreading in random complex net- works. Our objective is to elect leader nodes or communities of the network, which may spread the content among all nodes faster. We consider a well- known SPREAD algorithm by Mosk-Aoyama and Shah (2006), which provides the spreading and the growth of the node set possessing the information. Assum- ing that all nodes have asynchronous clocks, the next node is chosen uniformly among nodes of the network by the global clock tick according to a Poisson pro- cess. The extremal index measures the clustering tendency of high threshold exceedances. The node extremal index shows the ability to attract highly ranked nodes in its orbit. Considering a closeness centrality as a measure of a node’s leadership, we find the relation between its extremal index and the minimal spreading time.