Influence Maximization Based on Network Motifs in Mobile Social Networks

Abstract

A mobile social network (MSN) is a mobile communications system that involves the social relationship of the users, in such a network, mobile users can spread information, opinions, ideas, rumors. Influence Maximization (IM) aims to identify <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> nodes from a network such that the influence spread generated by the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> nodes is maximized, which has been attracting increasing attention in recent years. However, existing methods of influence maximization are heuristic algorithms based on network topology and greedy algorithms based on spreading. Accordingly, in this paper, we focused on Network Motifs (NM) as drivers of influence to impact the spreading process, we proposed IM-NM, a network motifs-based influence maximation scheme for delivering information efficiently. In consideration of the communication relationship and the users’ attributes, we first defined Weight Ratio (WR), Degree Density (DD), and Structural Stability Level (SSL). Then we identified the key network motifs by Naive Bayesian machine learning. Finally, we adopted the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> key network motifs as the unit structure to reconstruct the network, and select the bridge node with strong communication ability in the key motifs to maximize the information. We implement our proposed methods on a set of real-world networks to evaluate the performance, the experimental results demonstrate that our proposal achieves better performance than other related methods.