# Substitute Seed Nodes Mining Algorithms for Influence Maximization in Multi-Social Networks
## 1 Introduction  
In recent years, various social networks [1] offering different services have appeared on the Internet, e.g., Facebook, Twitter, YouTube and Foursquare. For the purpose of enjoying different services, some users register accounts on different social networks simultaneously. Different from the traditional connections with other users, they have not only social links among users within one social network, but also crossing links connecting accounts between different social networks. Multi-social networks are connected by these shared users [2]. Due to their obvious advantages in spreading information, as exemplified by the high speed, low cost and wide influence, social networks attract more and more attention of researchers, which results in many hot topics, involving social information spreading [3], public opinion [4], Internet marketing [5] and so on. The influence maximization in a social network has been extensively studied in the academic community [6; 7; 8; 9; 10], which is the problem of finding a small subset of nodes in a social network that could maximize the spread of influence [7]. However, the existing influence maximization research for the single social network cannot be directly adapted to the multi-social networks due to their heterogeneous architecture and complex connections among users. The users with multiple social network accounts can spread information from social network A to social network B. An example is given in Figure 1, a user who is registered on Twitter and Facebook has the ability to forward the information on Twitter to Facebook, which demonstrates the scope of information spreading no longer confined within the single social network. This factorleads to the different characteristics of information spreading as before and needs to be considered in the influence of maximization research. To maximize the influence spreading in multi-social networks, the researchers in References [11; 12; 13; 14; 15; 16] focus on finding \(k\) (\(k\in N^{*}\)) users to constitute the initial active seed node set \(S\) to spread information, the expected number of active nodes \(R(S)\) at the end of a diffusion process in multi-social networks can be maximized. Due to budgetary constraints, the size of \(S\) is usually fixed in existing research, i.e., \(k\) is fixed. However, when we get \(S\) through complex theoretical calculations, some initial seed nodes in the set \(S\) may be difficult to activate for some reasons. In the end, a broken \(S\) cannot get the maximum influence, resulting in the low influence spreading performance. For example, in social network advertising marketing, one user has high influence in social networks, but for some reasons, he is unwilling to post advertisements, which may lead to advertising marketing failure. Therefore, when some users in \(S\) cannot be activated, it is very necessary to find substitutes for these nodes to reduce the loss of influence. Some researchers have already done some work on this subject. [PERSON] et al. [17] proposed the idea of finding \"successors\". When a seed node cannot be activated, the neighbor node is selected as a substitute. [PERSON] et al. [18] named this problem as the Substitutes Discovery in Influence Maximization and proposed three solving algorithms based on the Greedy algorithms. However, these two works aim at solving the substitute mining problem in a single social network, which cannot adapt to the information spread in multi-social networks directly. In this paper, we discuss the information spread across social networks and focus on solving the problem of multi-social networks influence maximization. Specifically, the contributions of this paper are summarized as follows:  
1. We analyze the characteristics of information spreading in multi-social networks and define the special use with multiple social network accounts as _Bridge User_, which plays an important role in forwarding information from one social network to another. 2.