Scalable Method for Information Spread Control in Social Networks

1. Introduction

The most common way to grasp real world phenomena is to distinguish objects (elements, entities) and relations (interactions etc.) between them. From a global perspective the entities and their relations form networks. The distribution of relations is usually not uniform and hence some structures of elements and their relations may be distinguished. Mining such structures has the potential of discovering new knowledge about the network or its parts or even members. One of the basic ways of network mining is splitting of the network or rather its representation as a graph, into clusters. Clusters are groups of nodes which are interconnected in a way distinguishing them from the surrounding network. These groups or subsets of nodes are usually characterized by a denser set of relations. Such subsets (clusters) can be interpreted in various ways. This creates a necessity for algorithms that can cope with diversity of possible meanings. Commonness of networks in everyday life (e.g. the Internet, data sets of citings) implies using advanced methods to analyze them. The most common and natural coding method for networks are graphs. Graph structure and the way of information spread in networks are the most interesting fields of research in social network community detection. In this paper scalable method of cluster analysis based on random walks is presented. The method divides a graph into subsets, where some of them can be used for information spread control. The main aim of the algorithm presented in this paper is to detect dense subgraphs which can be interpreted as tight communities and to detect relatively sparse subgraphs interconnecting them called bridges, as they are deemed to bridge information spread between the tight communities. The method provides clustering sensitive to vertices assignment uncertainty. As a result of introduced Parallelized Locally Aggregated Random Walks (ParaLARW) algorithm one receives division which distinguishes sparse groups of nodes responsible for signal transfer between clusters.