The virtuality and openness of online social platforms make networks a hotbed for the rapid propagation of various rumors.In order to block the outbreak of rumor,one of the most effective containment measures is sprea...The virtuality and openness of online social platforms make networks a hotbed for the rapid propagation of various rumors.In order to block the outbreak of rumor,one of the most effective containment measures is spreading positive information to counterbalance the diffusion of rumor.The spreading mechanism of rumors and effective suppression strategies are significant and challenging research issues.Firstly,in order to simulate the dissemination of multiple types of information,we propose a competitive linear threshold model with state transition(CLTST)to describe the spreading process of rumor and anti-rumor in the same network.Subsequently,we put forward a community-based rumor blocking(CRB)algorithm based on influence maximization theory in social networks.Its crucial step is to identify a set of influential seeds that propagate anti-rumor information to other nodes,which includes community detection,selection of candidate anti-rumor seeds and generation of anti-rumor seed set.Under the CLTST model,the CRB algorithm has been compared with six state-of-the-art algorithms on nine online social networks to verify the performance.Experimental results show that the proposed model can better reflect the process of rumor propagation,and review the propagation mechanism of rumor and anti-rumor in online social networks.Moreover,the proposed CRB algorithm has better performance in weakening the rumor dissemination ability,which can select anti-rumor seeds in networks more accurately and achieve better performance in influence spread,sensitivity analysis,seeds distribution and running time.展开更多
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 i...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.展开更多
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 ...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.展开更多
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 e...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.展开更多
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...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(11=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.展开更多
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 exi...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.展开更多
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 ...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.展开更多
Influence maximization(IM)algorithms play a significant role in hypergraph analysis tasks,such as epidemic control analysis,viral marketing,and social influence analysis,and various IM algorithms have been proposed.Th...Influence maximization(IM)algorithms play a significant role in hypergraph analysis tasks,such as epidemic control analysis,viral marketing,and social influence analysis,and various IM algorithms have been proposed.The main challenge lies in IM algorithm evaluation,due to the complexity and diversity of the spreading processes of different IM algorithms in different hypergraphs.Existing evaluation methods mainly leverage statistical metrics,such as influence spread,to quantify overall performance,but do not fully unravel spreading characteristics and patterns.In this paper,we propose an exploratory visual analytics system,IMVis,to assist users in exploring and evaluating IM algorithms at the overview,pattern,and node levels.A spreading pattern mining method is first proposed to characterize spreading processes and extract important spreading patterns to facilitate efficient analysis and comparison of IM algorithms.Novel visualization glyphs are designed to comprehensively reveal both temporal and structural features of IM algorithms’spreading processes in hypergraphs at multiple levels.The effectiveness and usefulness of IMVis are demonstrated through two case studies and expert interviews.展开更多
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 t...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.展开更多
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 ...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.展开更多
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 se...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.展开更多
基金supported by the National Social Science Fund of China (Grant No.23BGL270)。
文摘The virtuality and openness of online social platforms make networks a hotbed for the rapid propagation of various rumors.In order to block the outbreak of rumor,one of the most effective containment measures is spreading positive information to counterbalance the diffusion of rumor.The spreading mechanism of rumors and effective suppression strategies are significant and challenging research issues.Firstly,in order to simulate the dissemination of multiple types of information,we propose a competitive linear threshold model with state transition(CLTST)to describe the spreading process of rumor and anti-rumor in the same network.Subsequently,we put forward a community-based rumor blocking(CRB)algorithm based on influence maximization theory in social networks.Its crucial step is to identify a set of influential seeds that propagate anti-rumor information to other nodes,which includes community detection,selection of candidate anti-rumor seeds and generation of anti-rumor seed set.Under the CLTST model,the CRB algorithm has been compared with six state-of-the-art algorithms on nine online social networks to verify the performance.Experimental results show that the proposed model can better reflect the process of rumor propagation,and review the propagation mechanism of rumor and anti-rumor in online social networks.Moreover,the proposed CRB algorithm has better performance in weakening the rumor dissemination ability,which can select anti-rumor seeds in networks more accurately and achieve better performance in influence spread,sensitivity analysis,seeds distribution and running time.
基金This research was supported in part by the Chinese National Natural Science Foundation under grant Nos.61602202 and 61702441the Natural Science Foundation of Jiangsu Province under contracts BK20160428 and BK20161302the Six talent peaks project in Jiangsu Province under contract XYDXX-034 and the project in Jiangsu Association for science and technology.
文摘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.
基金Thiswork is supported by theYouth Science and Technology Innovation Personnel Training Project of Heilongjiang(No.UNPYSCT-2020072)the FundamentalResearch Funds for the Universities of Heilongjiang(Nos.145109217,135509234)+1 种基金the Education Science Fourteenth Five-Year Plan 2021 Project of Heilongjiang(No.GJB1421344)the Innovative Research Projects for Postgraduates of Qiqihar University(No.YJSCX2022048).
文摘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.
基金Supported by the National Natural Science Foundation of China(No.62172352,61871465,42002138)the Natural Science Foundation of Hebei Province(No.F2019203157)the Science and Technology Research Project of Hebei(No.ZD2019004)。
文摘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.
基金This research was supported in part by the Chinese National Natural Science Foundation under grant Nos.61602202 and 61702441the Natural Science Foundation of Jiangsu Province under contracts BK20160428 and BK20161302the Six talent peaks project in Jiangsu Province under contract XYDXX-034 and the project in Jiangsu Association for science and technology.
文摘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(11=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.
基金supported by the Fundamental Research Funds for the Universities of Heilongjiang(Nos.145109217,135509234)the Youth Science and Technology Innovation Personnel Training Project of Heilongjiang(No.UNPYSCT-2020072)the Innovative Research Projects for Postgraduates of Qiqihar University(No.YJSCX2022048).
文摘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.
基金Project supported by the Zhejiang Provincial Natural Science Foundation (Grant No.LQ20F020011)the Gansu Provincial Foundation for Distinguished Young Scholars (Grant No.23JRRA766)+1 种基金the National Natural Science Foundation of China (Grant No.62162040)the National Key Research and Development Program of China (Grant No.2020YFB1713600)。
文摘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.
基金Zhejiang Provincial Natural Science Foundation of China(LQ22F020017)National Natural Science Foundation of China(62302137)Open Project Program of the State Key Lab of CAD&CG of Zhejiang University(A2104).
文摘Influence maximization(IM)algorithms play a significant role in hypergraph analysis tasks,such as epidemic control analysis,viral marketing,and social influence analysis,and various IM algorithms have been proposed.The main challenge lies in IM algorithm evaluation,due to the complexity and diversity of the spreading processes of different IM algorithms in different hypergraphs.Existing evaluation methods mainly leverage statistical metrics,such as influence spread,to quantify overall performance,but do not fully unravel spreading characteristics and patterns.In this paper,we propose an exploratory visual analytics system,IMVis,to assist users in exploring and evaluating IM algorithms at the overview,pattern,and node levels.A spreading pattern mining method is first proposed to characterize spreading processes and extract important spreading patterns to facilitate efficient analysis and comparison of IM algorithms.Novel visualization glyphs are designed to comprehensively reveal both temporal and structural features of IM algorithms’spreading processes in hypergraphs at multiple levels.The effectiveness and usefulness of IMVis are demonstrated through two case studies and expert interviews.
基金The authors are grateful to the anonymous reviewers and the editor for their valuable comments and suggestions.This work is supported by Natural Science Foundation of China(Grant Nos.61702066 and 11747125)Major Project of Science and Technology Research Program of Chongqing Education Commission of China(Grant No.KJZD-M201900601)+3 种基金Chongqing Research Program of Basic Research and Frontier Technology(Grant Nos.cstc2017jcyjAX0256 and cstc2018jcy-jAX0154)Project Supported by Chongqing Municipal Key Laboratory of Institutions of Higher Education(Grant No.cqupt-mct-201901)Tech-nology Foundation of Guizhou Province(QianKeHeJiChu[2020]1Y269)New academic seedling cultivation and exploration innovation project(QianKeHe Platform Talents[2017]5789-21).
文摘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.
基金This work is supported in part by the National Natural Science Foundation of China under Grant No.61672022.
文摘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.
基金the National Science Foundation(NSF)grants Computer and Network Systems(CNS)1824440,CNS 1828363,CNS 1757533,CNS 1618398,CNS 1651947,and CNS 1564128。
文摘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.
