Scalable Method for Information Spread Control in Social Networks

Scalable Method for Information Spread Control in Social Networks

Michal Wojtasiewicz (Polish Academy of Sciences, Poland) and Mieczysław Kłopotek (Polish Academy of Sciences, Poland)
DOI: 10.4018/978-1-5225-2814-2.ch014


In this chapter, scalable and parallelized method for cluster analysis based on random walks is presented. The aim of the algorithm introduced in this chapter is to detect dense sub graphs (clusters) and sparse sub graphs (bridges) which are responsible for information spreading among found clusters. The algorithm is sensitive to the uncertainty involved in assignment of vertices. It distinguishes groups of nodes that form sparse clusters. These groups are mostly located in places crucial for information spreading so one can control signal propagation between separated dense sub graphs by using algorithm provided in this work. Authors have also proposed new coefficient which measures quality of given clustering with respect to information spread control between clusters. Measures presented in this paper can be used for determining quality of whole partitioning or a single bridge.
Chapter Preview

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.

Complete Chapter List

Search this Book: