A thorough technical account, this paper addresses an important emerging opportunity in mobile social networks: viral marketing.
The proposed research aims to find a way to optimize the process of information diffusion within social networks by identifying the minimal number of individual nodes through which the information will be diffused as soon as possible. For this purpose, the authors adopt a diffusion minimization approach defined as an asymmetric k-center problem, and propose a community-based algorithm and a distributed set cover algorithm to meet the performance and time complexity requirements of large-scale mobile social networks and thus go beyond the state of the art.
The community-based algorithm exploits the concept of social relations by regarding as community a set of nodes where they have more connections inside the community than outside of the community, and by working with the community structure, for example, the structure of the network. For this, the central node and diffusion radius are introduced, and a method to define the diffusion modes within the community is provided. The distributed set cover algorithm allows for dealing with up-to-date information. In it, each node of the network collects up-to-date information and this information is used to determine the minimal number of diffusion nodes. This algorithm regards the set of nodes to which a given node can diffuse information for a certain period of time--a diffusion set--and identifies the k-node set maximizing “the union of the diffusion sets for the selected nodes.”
The paper presents a detailed description of the two algorithms and an evaluation comparing the two of them separately with state-of-the-art algorithms, such as the approximation algorithm, and concludes that the community-based algorithms display the best performance.
This paper, which contains a very well-described problem statement and review of related work covering all aspects of the addressed problem and motivating the need and the purpose of the proposed approach, is a great read for engineers, scientists, and scholars interested in information management in general and information management in social networks in particular.