RESUMEN

Selecting a set of initial users from a social network in order to maximize the envisaged number of influenced users is known as influence maximization (IM). Researchers have achieved significant advancements in the theoretical design and performance gain of several classical approaches, but these advances are almost reaching their pinnacle. Learning-based IM approaches have emerged recently with a higher generalization to unknown graphs than conventional methods. The development of learning-based IM methods is still constrained by a number of fundamental hardships, including (1) solving the objective function efficiently, (2) struggling to characterize the diverse underlying diffusion patterns, and (3) adapting the solution to different node-centrality-constrained IM variants. To address the aforementioned issues, we design a novel framework DeepIM for generatively characterizing the latent representation of seed sets, as well as learning the diversified information diffusion pattern in a data-driven and end-to-end way. Subsequently, we design a novel objective function to infer optimal seed sets under flexible node-centrality-based budget constraints. Extensive analyses are conducted over both synthetic and real-world datasets to demonstrate the overall performance of DeepIM.

RESUMEN

Peer effects can directly or indirectly rely on interaction networks to drive people to follow ideas or behaviours triggered by a few individuals, and such effects can be largely improved by targeting the so-called influential individuals. In this article, we study the current most promising seeding strategy used in field experiments, the one-hop strategy, where the underlying interaction networks are generally too impractical or prohibitively expensive to be obtained, and propose an individual-centralized seeding approach to target influential seeds in information-limited networks. The presented strategy works by reasonable follow-up questions to respondents, such as Who do you think has more connections/friends?, and constructs the seeding set by those nodes with the most nominations. In this manner, the proposed method could acquire more information about the studied interaction network from the inference of respondents without surveying additional individuals. We evaluate our strategy on networks from various experimental datasets. Results show that the obtained seeds are much more influential compared to the one-hop strategy and other methods. We also show how the proposed approach could be implemented in field studies and potentially provide better interventions in real scenarios.

Asunto(s)

RESUMEN

Balanced influence maximization aims to balance the influence maximization of multiple different entities in social networks and avoid the emergence of filter bubbles and echo chambers. Recently, an increasing number of studies have drawn attention to the study of balanced influence maximization in social networks and achieves success to some extent. However, most of them still have two major shortcomings. First, the previous works mainly focus on spreading the influence of multiple target entities to more users, ignoring the potential influence of the correlation between the target entities and other entities on information propagation in real social networks. Second, the existing methods require a large amount of diffusion sampling for influence estimation, making it difficult to apply to large social networks. To this end, we propose a Balanced Influence Maximization framework based on Deep Reinforcement Learning named BIM-DRL, which consists of two core components: an entity correlation evaluation module and a balanced seed node selection module. Specifically, in the entity correlation evaluation module, an entity correlation evaluation model based on the users' historical behavior sequences is proposed, which can accurately evaluate the impact of entity correlation on information propagation. In the balanced seed node selection module, a balanced influence maximization model based on deep reinforcement learning is designed to train the parameters in the objective function, and then a set of seed nodes that maximize the balanced influence is found. Extensive experiments on six real-life network datasets demonstrate the superiority of the BIM-DRL over state-of-the-art methods on the metrics of balanced influence spread and balanced propagation accuracy.

Asunto(s)

RESUMEN

Incorporating social factors into disease prevention and control efforts is an important undertaking of behavioral epidemiology. The interplay between disease transmission and human health behaviors, such as vaccine uptake, results in complex dynamics of biological and social contagions. Maximizing intervention adoptions via network-based targeting algorithms by harnessing the power of social contagion for behavior and attitude changes largely remains a challenge. Here we address this issue by considering a multiplex network setting. Individuals are situated on two layers of networks: the disease transmission network layer and the peer influence network layer. The disease spreads through direct close contacts while vaccine views and uptake behaviors spread interpersonally within a potentially virtual network. The results of our comprehensive simulations show that network-based targeting with pro-vaccine supporters as initial seeds significantly influences vaccine adoption rates and reduces the extent of an epidemic outbreak. Network targeting interventions are much more effective by selecting individuals with a central position in the opinion network as compared to those grouped in a community or connected professionally. Our findings provide insight into network-based interventions to increase vaccine confidence and demand during an ongoing epidemic.

RESUMEN

Recently, a new subject known as the Social Internet of Things (SIoT) has been presented based on the integration the Internet of Things and social network concepts. SIoT is increasingly popular in modern human living, including applications such as smart transportation, online health care systems, and viral marketing. In advertising based on SIoT, identifying the most effective diffuser nodes to maximize reach is a critical challenge. This article proposes an efficient heuristic algorithm named Influence Maximization of advertisement for Social Internet of Things (IMSoT), inspired by real-world advertising. The IMSoT algorithm consists of two steps: selecting candidate objects and identifying the final seed set. In the first step, influential candidate objects are selected based on factors, such as degree, local importance value, and weak and sensitive neighbors set. In the second step, effective influence is calculated based on overlapping between candidate objects to identify the appropriate final seed set. The IMSoT algorithm ensures maximum influence and minimum overlap, reducing the spreading caused by the seed set. A unique feature of IMSoT is its focus on preventing duplicate advertising, which reduces extra costs, and considering weak objects to reach the maximum target audience. Experimental evaluations in both real-world and synthetic networks demonstrate that our algorithm outperforms other state-of-the-art algorithms in terms of paying attention to weak objects by 38%-193% and in terms of preventing duplicate advertising (reducing extra cost) by 26%-77%. Additionally, the running time of the IMSoT algorithm is shorter than other state-of-the-art algorithms.

RESUMEN

Thanks to the mass adoption of internet and mobile devices, users of the social media can seamlessly and spontaneously connect with their friends, followers and followees. Consequently, social media networks have gradually become the major venue for broadcasting and relaying information, and is casting great influences on the people in many aspects of their daily lives. Thus locating those influential users in social media has become crucially important for the successes of many viral marketing, cyber security, politics, and safety-related applications. In this study, we address the problem through solving the tiered influence and activation thresholds target set selection problem, which is to find the seed nodes that can influence the most users within a limited time frame. Both the minimum influential seeds and maximum influence within budget problems are considered in this study. Besides, this study proposes several models exploiting different requirements on seed nodes selection, such as maximum activation, early activation and dynamic threshold. These time-indexed integer program models suffer from the computational difficulties due to the large numbers of binary variables to model influence actions at each time epoch. To address this challenge, this paper designs and leverages several efficient algorithms, i.e., Graph Partition, Nodes Selection, Greedy algorithm, recursive threshold back algorithm and two-stage approach in time, especially for large-scale networks. Computational results show that it is beneficial to apply either the breadth first search or depth first search greedy algorithms for the large instances. In addition, algorithms based on node selection methods perform better in the long-tailed networks.

RESUMEN

The influence maximization (IM) problem is defined as identifying a group of influential nodes in a network such that these nodes can affect as many nodes as possible. Due to its great significance in viral marketing, disease control, social recommendation, and so on, considerable efforts have been devoted to the development of methods to solve the IM problem. In the literature, VoteRank and its improved algorithms have been proposed to select influential nodes based on voting approaches. However, in the voting process of these algorithms, a node cannot vote for itself. We argue that this voting schema runs counter to many real scenarios. To address this issue, we designed the VoteRank* algorithm, in which we first introduce the self-voting mechanism into the voting process. In addition, we also take into consideration the diversities of nodes. More explicitly, we measure the voting ability of nodes and the amount of a node voting for its neighbors based on the H-index of nodes. The effectiveness of the proposed algorithm is experimentally verified on 12 benchmark networks. The results demonstrate that VoteRank* is superior to the baseline methods in most cases.

Asunto(s)

RESUMEN

The social media podium offers a communal perspective platform for web marketing, advertisement, political campaign, etc. It structures like-minded end-users over the explicit group as a community. Community structure over social media is the collaborative group of globally spread users having similar interests regarding a communal topic, product or any other axis. In recent years, researchers have widely used clustering techniques of data mining to structure communities over social media. Still, due to a lack of network and implicit communal information, researchers cannot bind mutually robust and modular community structures. The collaborative features of social media are inherent with implicit and explicit end-users. The explicit nature of both active and passive users is easily extracted from the graphical structure of social media. On the other hand, the degree of information inclusion of implicit features depends upon end-users participation. The Implicit features of frequently active users are diversely available, while integrating passive and silent users' implicit features over the community is tedious. This work proposed a social theory based influence maximization (STIM) framework for community detection over social media. It combines user-generated content with profile information, extracts passive social media users through influence maximization, and provides the user space for influencing inactive users. The STIM framework clusters identical nodes over the maximum influencing node axis based on their graphical parameters such as node degree, node similarity, node reachability, modularity, and node density. This framework also provides the structural, relational and mathematical concept for the functional grouping of like-minded people as a community over social media through social theory. Finally, an evaluation has been carried out over six real-time datasets. It analyses that convolution neural network over STIM structure more dense and modular communities via influence maximization. STIM acquired around 93% modularity and 94% Normalized Mutual Information (NMI), resulting in approximately 2.23% and 5.69% improvements in modularity and NMI, respectively, over the best-acquired result of the benchmark approach.

RESUMEN

BACKGROUND: Essential proteins are indispensable to the development and survival of cells. The identification of essential proteins not only is helpful for the understanding of the minimal requirements for cell survival, but also has practical significance in disease diagnosis, drug design and medical treatment. With the rapidly amassing of protein-protein interaction (PPI) data, computationally identifying essential proteins from protein-protein interaction networks (PINs) becomes more and more popular. Up to now, a number of various approaches for essential protein identification based on PINs have been developed. RESULTS: In this paper, we propose a new and effective approach called iMEPP to identify essential proteins from PINs by fusing multiple types of biological data and applying the influence maximization mechanism to the PINs. Concretely, we first integrate PPI data, gene expression data and Gene Ontology to construct weighted PINs, to alleviate the impact of high false-positives in the raw PPI data. Then, we define the influence scores of nodes in PINs with both orthological data and PIN topological information. Finally, we develop an influence discount algorithm to identify essential proteins based on the influence maximization mechanism. CONCLUSIONS: We applied our method to identifying essential proteins from saccharomyces cerevisiae PIN. Experiments show that our iMEPP method outperforms the existing methods, which validates its effectiveness and advantage.

Asunto(s)

RESUMEN

The connection between users in social networks can be maintained for a certain period of time, and the static network structure formed provides the basic conditions for various kinds of research, especially for discovering customer groups that can generate great influence, which is important for product promotion, epidemic prevention and control, and public opinion supervision, etc. However, the computational process of influence maximization ignores the timeliness of interaction behaviors among users, the screened target users cannot diffuse information well, and the time complexity of relying on greedy rules to handle the influence maximization problem is high. Therefore, this paper analyzes the influence of the interaction between nodes in dynamic social networks on information dissemination, extends the classical independent cascade model to a dynamic social network dissemination model based on effective links, and proposes a two-stage influence maximization solution algorithm (Outdegree Effective Link-OEL) based on node degree and effective links to enhance the efficiency of problem solving. In order to verify the effectiveness of the algorithm, five typical influence maximization methods are compared and analyzed on four real data sets. The results show that the OEL algorithm has good performance in propagation range and running time.

RESUMEN

Mathematical approaches, such as compartmental models and agent-based models, have been utilized for modeling the spread of the infectious diseases in the computational epidemiology. However, the role of social network structure for transmission of diseases is not explicitly considered in these models. In this paper, the influence maximization problem, considering the diseases starting at some initial nodes with the potential to maximize the spreading in a social network, is adapted to model the spreading process. This approach includes the analysis of network structure and the modeling of connections among individuals with probabilities to be infected. Additionally, individual behaviors that change along the time and eventually influence the spreading process are also included. These considerations are formulated by integer optimization models. Simulation results, based on the randomly generated networks and a local community network under the COVID-19, are performed to validate the effectiveness of the proposed models, and their relationships to the classic compartmental models.

RESUMEN

Many transport systems in the real world can be modeled as networked systems. Due to limited resources, only a few nodes can be selected as seeds in the system, whose role is to spread required information or control signals as widely as possible. This problem can be modeled as the influence maximization problem. Most of the existing selection strategies are based on the invariable network structure and have not touched upon the condition that the network is under structural failures. Related studies indicate that such strategies may not completely tackle complicated diffusion tasks in reality, and the robustness of the information diffusion process against perturbances is significant. To give a numerical performance criterion of seeds under structural failure, a measure has been developed to define the robust influence maximization (RIM) problem. Further, a memetic optimization algorithm (MA) which includes several problem-orientated operators to improve the search ability, termed RIMMA, has been presented to deal with the RIM problem. Experimental results on synthetic networks and real-world networks validate the effectiveness of RIMMA, its superiority over existing approaches is also shown.

RESUMEN

Ongoing COVID-19 pandemic poses many challenges to the research of artificial intelligence. Epidemics are important in network science for modeling disease spread over networks of contacts between individuals. To prevent disease spread, it is desirable to introduce prioritized isolation of the individuals contacting many and unspecified others, or connecting different groups. Finding such influential individuals in social networks, and simulating the speed and extent of the disease spread are what we need for combating COVID-19. This article focuses on the following topics, and discusses some of the traditional and emerging research attempts: (1) topics related to epidemics in network science, such as epidemic modeling, influence maximization and temporal networks, (2) recent research of network science for COVID-19 and (3) datasets and resources for COVID-19 research.

RESUMEN

BACKGROUND: Identifying the most important genes in a cancer gene network is a crucial step in understanding the disease's functional characteristics and finding an effective drug. METHOD: In this study, a popular influence maximization technique was applied on a large breast cancer gene network to identify the most influential genes computationally. The novel approach involved incorporating gene expression data and protein to protein interaction network to create a customized pruned and weighted gene network. This was then readily provided to the influence maximization procedure. The weighted gene network was also processed through a widely accepted framework that identified essential proteins to benchmark the proposed method. RESULTS: The proposed method's results had matched with the majority of the output from the benchmarked framework. The key takeaway from the experiment was that the influential genes identified by the proposed method, which did not match favorably with the widely accepted framework, were found to be very important by previous in-vivo studies on breast cancer. INTERPRETATION & CONCLUSION: The new findings generated from the proposed method give us a favorable reason to infer that influence maximization added a more diversified approach to define and identify important genes and could be incorporated with other popular computational techniques for more relevant results.

Asunto(s)

RESUMEN

The main goal in the influence maximization problem (IMP) is to find k minimum nodes with the highest influence spread on the social networks. Since IMP is NP-hard and is not possible to obtain the optimum results, it is considered by heuristic algorithms. Many strategies focus on the power of the influence spread of core nodes to find k influential nodes. Most of the core detection-based methods concentrate on nodes in the highest core and often give the same power for all nodes in the best core. However, some other nodes fairly have the potential to select as seed nodes in other less important cores, because these nodes can play an important role in the diffusion of information among the core nodes with other nodes. Given this fact, this article proposes a new shell-based ranking and filtering method, called shell-based ranking and filtering method (SRFM), for selecting influential seeds with the aim to maximize influence in the network. The proposed algorithm initially selects a set of nodes in different shells. Moreover, a set of the candidate nodes are created, and most of the periphery nodes are removed during a pruning approach to reduce the computational overhead. Therefore, the seed nodes are selected from the candidate nodes set using the role of the bridge nodes. Experimental results in both synthetic and real data sets showed that the proposed SRFM algorithm has more acceptable efficiency in the influence spread and runtime than other algorithms.

Asunto(s)

RESUMEN

Influence Maximization problem, selection of a set of users in a social network to maximize the influence spread, has received ample research attention in the social network analysis domain due to its practical applications. Although the problem has been extensively studied, existing works have neglected the location's popularity and importance along with influential users for product promotion at a particular region in Location-based Social Networks. Real-world marketing companies are more interested in finding suitable locations and influential users in a city to promote their product and attract as many users as possible. In this work, we study the joint selection of influential users and locations within a target region from two complementary perspectives; general and specific location type selection perspectives. The first is to find influential users and locations at a specified region irrespective of location type or category. The second perspective is to recommend locations matching location preference in addition to the target region for product promotion. To address general and specific location recommendations and influential users, we propose heuristic-based methods that effectively find influential users and locations for product promotion. Our experimental results show that it is not always an optimal choice to recommend locations with the highest popularity values, such as ratings, check-ins, and so, which may not be a true indicator of location popularity to be considered for marketing. Our results show that not only influential users are helpful for product promotion, but suitable influential locations can also assist in promoting products in the target region.

RESUMEN

BACKGROUND: An effective approach to containing epidemic outbreaks (e.g., COVID-19) is targeted immunization, which involves identifying "super spreaders" who play a key role in spreading disease over human contact networks. The ultimate goal of targeted immunization and other disease control strategies is to minimize the impact of outbreaks. It shares similarity with the famous influence maximization problem studied in the field of social network analysis, whose objective is to identify a group of influential individuals to maximize the influence spread over social networks. This study aims to establish the equivalence of the two problems and develop an effective methodology for targeted immunization through the use of influence maximization. METHODS: We present a concise formulation of the targeted immunization problem and show its equivalence to the influence maximization problem under the framework of the Linear Threshold diffusion model. Thus the influence maximization problem, as well as the targeted immunization problem, can be solved by an optimization approach. A Benders' decomposition algorithm is developed to solve the optimization problem for effective solutions. RESULTS: A comprehensive computational study is conducted to evaluate the performance and scalability of the optimization approach on real-world large-scale networks. Computational results show that our proposed approaches achieve more effective solutions compared to existing methods. CONCLUSIONS: We show the equivalence of the outbreak minimization and influence maximization problems and present a concise formulation for the influence maximization problem under the Linear Threshold diffusion model. A tradeoff between computational effectiveness and computational efficiency is illustrated. Our results suggest that the capability of determining the optimal group of individuals for immunization is particularly crucial for the containment of infectious disease outbreaks within a small network. Finally, our proposed methodology not only determines the optimal solutions for target immunization, but can also aid policymakers in determining the right level of immunization coverage.

Asunto(s)

RESUMEN

Social networks provide us a convenient platform to communicate and share information or ideas with each other, but it also causes many negative effects at the same time, such as, the spread of misinformation or rumor in social networks may cause public panic and even serious economic or political crisis. In this paper, we propose a Community-based Rumor Blocking Problem (CRBMP), i.e., selecting a set of seed users from all communities as protectors with the constraint of budget b such that the expected number of users eventually not being influenced by rumor sources is maximized. We consider the community structure in social networks and solve our problem in two stages, in the first stage, we allocate budget b for all the communities, this sub-problem whose objective function is proved to be monotone and DR-submodular, so we can use the method of submodular function maximization on an integer lattice, which is different from most of the existing work with the submodular function over a set function. Then a greedy community budget allocation algorithm is devised to get an 1 - 1 / e approximation ratio; we also propose a speed-up greedy algorithm which greatly reduces the time complexity for the community budget allocation and can get an 1 - 1 / e - ϵ approximation guarantee meanwhile. Next we solve the Protector Seed Selection (PSS) problem in the second stage after we obtained the budget allocation vector for communities, we greedily choose protectors for each community with the budget constraints to achieve the maximization of the influence of protectors. The greedy algorithm for PSS problem can achieve a 1/2 approximation guarantee. We also consider a special case where the rumor just originates from one community and does not spread out of its own community before the protectors are selected, the proposed algorithm can reduce the computational cost than the general greedy algorithm since we remove the uninfected communities. Finally, we conduct extensive experiments on three real world data sets, the results demonstrate the effectiveness of the proposed algorithm and its superiority over other methods.

RESUMEN

BACKGROUND: Gastrointestinal (GI) cancer including colorectal cancer, gastric cancer, pancreatic cancer, etc., are among the most frequent malignancies diagnosed annually and represent a major public health problem worldwide. METHODS: This paper reports an aided curation pipeline to identify potential influential genes for gastrointestinal cancer. The curation pipeline integrates biomedical literature to identify named entities by Bi-LSTM-CNN-CRF methods. The entities and their associations can be used to construct a graph, and from which we can compute the sets of co-occurring genes that are the most influential based on an influence maximization algorithm. RESULTS: The sets of co-occurring genes that are the most influential that we discover include RARA - CRBP1, CASP3 - BCL2, BCL2 - CASP3 - CRBP1, RARA - CASP3 - CRBP1, FOXJ1 - RASSF3 - ESR1, FOXJ1 - RASSF1A - ESR1, FOXJ1 - RASSF1A - TNFAIP8 - ESR1. With TCGA and functional and pathway enrichment analysis, we prove the proposed approach works well in the context of gastrointestinal cancer. CONCLUSIONS: Our pipeline that uses text mining to identify objects and relationships to construct a graph and uses graph-based influence maximization to discover the most influential co-occurring genes presents a viable direction to assist knowledge discovery for clinical applications.

Asunto(s)

RESUMEN

Cancer driver genes (CDGs) are the genes whose mutations cause tumor growth. Several computational methods have been previously developed for finding CDGs. Most of these methods are sequence-based, that is, they rely on finding key mutations in genomic data to predict CDGs. In the present work, we propose iMaxDriver as a network-based tool for predicting driver genes by application of influence maximization algorithm on human transcriptional regulatory network (TRN). In the first step of this approach, the TRN is pruned and weighted by exploiting tumor-specific gene expression (GE) data. Then, influence maximization approach is used to find the influence of each gene. The top genes with the highest influence rate are selected as the potential driver genes. We compared the performance of our CDG prediction method with fifteen other computational tools, based on a benchmark of three different cancer types. Our results show that iMaxDriver outperforms most of the state-of-the-art algorithms for CDG prediction. Furthermore, iMaxDriver is able to correctly predict many CDGs that are overlooked by all previously published tools. Due to this relative orthogonality, iMaxDriver can be considered as a complementary approach to the sequence-based CDG prediction methods.

Asunto(s)