An Influence Maximization Algorithm Based on Improved K-Shell in Temporal Social Networks

Influence maximization of temporal social networks(IMT)is a problem that aims to find the most influential set of nodes in the temporal network so that their information can be the most widely spread.To solve the IMT problem,we propose an influence maximization algorithm based on an improved K-shell method,namely improved K-shell in temporal social networks(KT).The algorithm takes into account the global and local structures of temporal social networks.First,to obtain the kernel value Ks of each node,in the global scope,it layers the network according to the temporal characteristic of nodes by improving the K-shell method.Then,in the local scope,the calculation method of comprehensive degree is proposed to weigh the influence of nodes.Finally,the node with the highest comprehensive degree in each core layer is selected as the seed.However,the seed selection strategy of KT can easily lose some influential nodes.Thus,by optimizing the seed selection strategy,this paper proposes an efficient heuristic algorithm called improved K-shell in temporal social networks for influence maximization(KTIM).According to the hierarchical distribution of cores,the algorithm adds nodes near the central core to the candidate seed set.It then searches for seeds in the candidate seed set according to the comprehensive degree.Experiments showthatKTIMis close to the best performing improved method for influence maximization of temporal graph(IMIT)algorithm in terms of effectiveness,but runs at least an order of magnitude faster than it.Therefore,considering the effectiveness and efficiency simultaneously in temporal social networks,the KTIM algorithm works better than other baseline algorithms.

An Influence Maximization Algorithm Based on the Mixed Importance of Nodes

The influence maximization is the problem of finding k seed nodes that maximize the scope of influence in a social network.Therefore,the comprehensive influence of node needs to be considered,when we choose the most influential node set consisted of k seed nodes.On account of the traditional methods used to measure the influence of nodes,such as degree centrality,betweenness centrality and closeness centrality,consider only a single aspect of the influence of node,so the influence measured by traditional methods mentioned above of node is not accurate.In this paper,we obtain the following result through experimental analysis:the influence of a node is relevant not only to its degree and coreness,but also to the degree and coreness of the n-order neighbor nodes.Hence,we propose a algorithm based on the mixed importance of nodes to measure the comprehensive influence of node,and the algorithm we proposed is simple and efficient.In addition,the performance of the algorithm we proposed is better than that of traditional influence maximization algorithms.

Time sequential influence maximization algorithm based on neighbor node influence

In view of the forwarding microblogging,secondhand smoke,happiness,and many other phenomena in real life,the spread characteristic of the secondary neighbor nodes in this kind of phenomenon and network scheduling is extracted,and sequence influence maximization problem based on the influence of neighbor nodes is proposed in this paper.That is,in the time sequential social network,the propagation characteristics of the second-level neighbor nodes are considered emphatically,and k nodes are found to maximize the information propagation.Firstly,the propagation probability between nodes is calculated by the improved degree estimation algorithm.Secondly,the weighted cascade model(WCM) based on static social network is not suitable for temporal social network.Therefore,an improved weighted cascade model(IWCM) is proposed,and a second-level neighbors time sequential maximizing influence algorithm(STIM) is put forward based on node degree.It combines the consideration of neighbor nodes and the problem of overlap of influence scope between nodes,and makes it chronological.Finally,the experiment verifies that STIM algorithm has stronger practicability,superiority in influence range and running time compared with similar algorithms,and is able to solve the problem of maximizing the timing influence based on the influence of neighbor nodes.

An Influence Maximization Algorithm Based on the Influence Propagation Range of Nodes

The problem of influence maximization in the social network G is to find k seed nodes with the maximum influence.The seed set S has a wider range of influence in the social network G than other same-size node sets.The influence of a node is usually established by using the IC model(Independent Cascade model)with a considerable amount of Monte Carlo simulations used to approximate the influence of the node.In addition,an approximate effect(1􀀀1=e)is obtained,when the number of Monte Carlo simulations is 10000 and the probability of propagation is very small.In this paper,we analyze that the propagative range of influence of node set is limited in the IC model,and we find that the influence of node only spread to the t0-th neighbor.Therefore,we propose a greedy algorithm based on the improved IC model that we only consider the influence in the t0-th neighbor of node.Finally,we perform experiments on 10 real social network and achieve favorable results.

Approximating Special Social Influence Maximization Problems

Social Influence Maximization Problems(SIMPs)deal with selecting k seeds in a given Online Social Network(OSN)to maximize the number of eventually-influenced users.This is done by using these seeds based on a given set of influence probabilities among neighbors in the OSN.Although the SIMP has been proved to be NP-hard,it has both submodular(with a natural diminishing-return)and monotone(with an increasing influenced users through propagation)that make the problem suitable for approximation solutions.However,several special SIMPs cannot be modeled as submodular or monotone functions.In this paper,we look at several conditions under which non-submodular or non-monotone functions can be handled or approximated.One is a profit-maximization SIMP where seed selection cost is included in the overall utility function,breaking the monotone property.The other is a crowd-influence SIMP where crowd influence exists in addition to individual influence,breaking the submodular property.We then review several new techniques and notions,including double-greedy algorithms and the supermodular degree,that can be used to address special SIMPs.Our main results show that for a specific SIMP model,special network structures of OSNs can help reduce its time complexity of the SIMP.

A Novel Influence Maximization Algorithm for a Competitive Environment Based on Social Media Data Analytics

Online social networks are increasingly connecting people around the world.Influence maximization is a key area of research in online social networks,which identifies influential users during information dissemination.Most of the existing influence maximization methods only consider the transmission of a single channel,but real-world networks mostly include multiple channels of information transmission with competitive relationships.The problem of influence maximization in an environment involves selecting the seed node set for certain competitive information,so that it can avoid the influence of other information,and ultimately affect the largest set of nodes in the network.In this paper,the influence calculation of nodes is achieved according to the local community discovery algorithm,which is based on community dispersion and the characteristics of dynamic community structure.Furthermore,considering two various competitive information dissemination cases as an example,a solution is designed for self-interested information based on the assumption that the seed node set of competitive information is known,and a novel influence maximization algorithm of node avoidance based on user interest is proposed.Experiments conducted based on real-world Twitter dataset demonstrates the efficiency of our proposed algorithm in terms of accuracy and time against notable influence maximization algorithms.

Maximizing Influence in Temporal Social Networks:A Node Feature-Aware Voting Algorithm

Influence Maximization(IM)aims to select a seed set of size k in a social network so that information can be spread most widely under a specific information propagation model through this set of nodes.However,most existing studies on the IM problem focus on static social network features,while neglecting the features of temporal social networks.To bridge this gap,we focus on node features reflected by their historical interaction behavior in temporal social networks,i.e.,interaction attributes and self-similarity,and incorporate them into the influence maximization algorithm and information propagation model.Firstly,we propose a node feature-aware voting algorithm,called ISVoteRank,for seed nodes selection.Specifically,before voting,the algorithm sets the initial voting ability of nodes in a personalized manner by combining their features.During the voting process,voting weights are set based on the interaction strength between nodes,allowing nodes to vote at different extents and subsequently weakening their voting ability accordingly.The process concludes by selecting the top k nodes with the highest voting scores as seeds,avoiding the inefficiency of iterative seed selection in traditional voting-based algorithms.Secondly,we extend the Independent Cascade(IC)model and propose the Dynamic Independent Cascade(DIC)model,which aims to capture the dynamic features in the information propagation process by combining node features.Finally,experiments demonstrate that the ISVoteRank algorithm has been improved in both effectiveness and efficiency compared to baseline methods,and the influence spread through the DIC model is improved compared to the IC model.

Identifying influential spreaders in social networks: A two-stage quantum-behaved particle swarm optimization with Lévy flight

The influence maximization problem aims to select a small set of influential nodes, termed a seed set, to maximize their influence coverage in social networks. Although the methods that are based on a greedy strategy can obtain good accuracy, they come at the cost of enormous computational time, and are therefore not applicable to practical scenarios in large-scale networks. In addition, the centrality heuristic algorithms that are based on network topology can be completed in relatively less time. However, they tend to fail to achieve satisfactory results because of drawbacks such as overlapped influence spread. In this work, we propose a discrete two-stage metaheuristic optimization combining quantum-behaved particle swarm optimization with Lévy flight to identify a set of the most influential spreaders. According to the framework,first, the particles in the population are tasked to conduct an exploration in the global solution space to eventually converge to an acceptable solution through the crossover and replacement operations. Second, the Lévy flight mechanism is used to perform a wandering walk on the optimal candidate solution in the population to exploit the potentially unidentified influential nodes in the network. Experiments on six real-world social networks show that the proposed algorithm achieves more satisfactory results when compared to other well-known algorithms.

Identifying influential nodes in social networks via community structure and influence distribution difference

This paper aims to effectively solve the problem of the influence maximization in social networks.For this purpose,an influence maximization method that can identify influential nodes via the community structure and the influence distribution difference is proposed.Firstly,the network embedding-based community detection approach is developed,by which the social network is divided into several high-quality communities.Secondly,the solution of influence maximization is composed of the candidate stage and the greedy stage.The candidate stage is to select candidate nodes from the interior and the boundary of each community using a heuristic algorithm,and the greedy stage is to determine seed nodes with the largest marginal influence increment from the candidate set through the sub-modular property-based Greedy algorithm.Finally,experimental results demonstrate the superiority of the proposed method compared with existing methods,from which one can further find that our work can achieve a good tradeoff between the influence spread and the running time.

Influence Diffusion Model in Multiplex Networks

The problem of influence maximizing in social networks refers to obtaining a set of nodes of a specified size under a specific propagation model so that the aggregation of the node-set in the network has the greatest influence.Up to now,most of the research has tended to focus on monolayer network rather than on multiplex networks.But in the real world,most individuals usually exist in multiplex networks.Multiplex networks are substantially different as compared with those of a monolayer network.In this paper,we integrate the multi-relationship of agents in multiplex networks by considering the existing and relevant correlations in each layer of relationships and study the problem of unbalanced distribution between various relationships.Meanwhile,we measure the distribution across the network by the similarity of the links in the different relationship layers and establish a unified propagation model.After that,place on the established multiplex network propagation model,we propose a basic greedy algorithm on it.To reduce complexity,we combine some of the characteristics of triggering model into our algorithm.Then we propose a novel MNStaticGreedy algorithm which is based on the efficiency and scalability of the StaticGreedy algorithm.Our experiments show that the novel model and algorithm are effective,efficient and adaptable.

AIGCrank:A new adaptive algorithm for identifying a set of influential spreaders in complex networks based on gravity centrality

The influence maximization problem in complex networks asks to identify a given size of seed spreaders set to maximize the number of expected influenced nodes at the end of the spreading process.This problem finds many practical applications in numerous areas such as information dissemination,epidemic immunity,and viral marketing.However,most existing influence maximization algorithms are limited by the“rich-club”phenomenon and are thus unable to avoid the influence overlap of seed spreaders.This work proposes a novel adaptive algorithm based on a new gravity centrality and a recursive ranking strategy,named AIGCrank,to identify a set of influential seeds.Specifically,the gravity centrality jointly employs the neighborhood,network location and topological structure information of nodes to evaluate each node's potential of being selected as a seed.We also present a recursive ranking strategy for identifying seed nodes one-byone.Experimental results show that our algorithm competes very favorably with the state-of-the-art algorithms in terms of influence propagation and coverage redundancy of the seed set.

Identifying multiple influential spreaders in complex networks based on spectral graph theory

One of the hot research topics in propagation dynamics is identifying a set of critical nodes that can influence maximization in a complex network.The importance and dispersion of critical nodes among them are both vital factors that can influence maximization.We therefore propose a multiple influential spreaders identification algorithm based on spectral graph theory.This algorithm first quantifies the role played by the local structure of nodes in the propagation process,then classifies the nodes based on the eigenvectors of the Laplace matrix,and finally selects a set of critical nodes by the constraint that nodes in the same class are not adjacent to each other while different classes of nodes can be adjacent to each other.Experimental results on real and synthetic networks show that our algorithm outperforms the state-of-the-art and classical algorithms in the SIR model.

An Operator-Based Approach for Modeling Influence Diffusion in Complex Social Networks

Social media have dramatically changed the mode of information dissemination.Various models and algorithms have been developed to model information diffusion and address the influence maximization problem in complex social networks.However,it appears difficult for state-of-the-art models to interpret complex and reversible real interactive networks.In this paper,we propose a novel influence diffusion model,i.e.,the Operator-Based Model(OBM),by leveraging the advantages offered from the heat diffusion based model and the agent-based model.The OBM improves the performance of simulated dissemination by considering the complex user context in the operator of the heat diffusion based model.The experiment obtains a high similarity of the OBM simulated trend to the real-world diffusion process by use of the dynamic time warping method.Furthermore,a novel influence maximization algorithm,i.e.,the Global Topical Support Greedy algorithm(GTS-Greedy algorithm),is proposed corresponding to the OBM.The experimental results demonstrate its promising performance by comparing it against other classic algorithms.

Efficient Algorithms for Maximizing Group Influence in Social Networks

In social network applications,individual opinion is often influenced by groups,and most decisions usually reflect the majority’s opinions.This imposes the group influence maximization(GIM) problem that selects k initial nodes,where each node belongs to multiple groups for a given social network and each group has a weight,to maximize the weight of the eventually activated groups.The GIM problem is apparently NP-hard,given the NP-hardness of the influence maximization(IM) problem that does not consider groups.Focusing on activating groups rather than individuals,this paper proposes the complementary maximum coverage(CMC) algorithm,which greedily and iteratively removes the node with the approximate least group influence until at most k nodes remain.Although the evaluation of the current group influence against each node is only approximate,it nevertheless ensures the success of activating an approximate maximum number of groups.Moreover,we also propose the improved reverse influence sampling(IRIS) algorithm through fine-tuning of the renowned reverse influence sampling algorithm for GIM.Finally,we carry out experiments to evaluate CMC and IRIS,demonstrating that they both outperform the baseline algorithms respective of their average number of activated groups under the independent cascade(IC)model.

Study on Information Diffusion Analysis in Social Networks and Its Applications

Due to the prevalence of social network services, more and more attentions are paid to explore how information diffuses and users affect each other in these networks, which has a wide range of applications, such as viral marketing, reposting prediction and social recommendation. Therefore, in this paper, we review the recent advances on information diffusion analysis in social networks and its applications. Specifically, we first shed light on several popular models to describe the information diffusion process in social networks, which enables three practical applications, i.e., influence evaluation, influence maximization and information source detection. Then, we discuss how to evaluate the authority and influence based on network structures. After that, current solutions to influence maximiza- tion and information source detection are discussed in detail, respectively. Finally, some possible research directions of information diffu- sion analysis are listed for further study.

Budget Allocation for Maximizing Viral Advertising in Social Networks

Viral advertising in social networks has arisen as one of the most promising ways to increase brand awareness and product sales. By distributing a limited budget, we can incentivize a set of users as initial adopters so that the advertising can start from the initial adopters and spread via sociM links to become viral. Despite extensive researches in how to target the most influential users, a key issue is often neglected： how to incentivize the initial adopters. In the problem of influence maximization, the assumption is that each user has a fixed cost for being initial adopters, while in practice, user decisions for accepting the budget to be initial adopters are often probabilistic rather than deterministic. In this paper, we study optimal budget allocation in social networks to maximize the spread of viral advertising. In particular, a concave probability model is introduced to characterize each user＇s utility for being an initial adopter. Under this model, we show that it is NP-hard to find an optimal budget allocation for maximizing the spread of viral advertising. We then present a novel discrete greedy algorithm with near optimal performance, and further propose scaling-up techniques to improve the time-efficiency of our algorithm. Extensive experiments on real-world social graphs are implemented to validate the effectiveness of our algorithm in practice. The results show that our algorithm can outperform other intuitive heuristics significantly in almost all cases.