A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks

Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-k nodes problem and 2) lambda-coverage problem. In the top-k nodes problem, we are required to find a set of k key nodes that would maximize the number of nodes being influenced in the network. The lambda-coverage problem is concerned with finding a set of k key nodes having minimal size that can influence a given percentage lambda of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-k nodes problem and the lambda-coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient. Note to Practitioners-In recent times, social networks have received a high level of attention due to their proven ability in improving the performance of web search, recommendations in collaborative filtering systems, spreading a technology in the market using viral marketing techniques, etc. It is well known that the interpersonal relationships (or ties or links) between individuals cause change or improvement in the social system because the decisions made by individuals are influenced heavily by the behavior of their neighbors. An interesting and key problem in social networks is to discover the most influential nodes in the social network which can influence other nodes in the social network in a strong and deep way. This problem is called the target set selection problem and has two variants: 1) the top-k nodes problem, where we are required to identify a set of k influential nodes that maximize the number of nodes being influenced in the network and 2) the lambda-coverage problem which involves finding a set of influential nodes having minimum size that can influence a given percentage lambda of the nodes in the entire network. There are many existing algorithms in the literature for solving these problems. In this paper, we propose a new algorithm which is based on a novel interpretation of information diffusion in a social network as a cooperative game. Using this analogy, we develop an algorithm based on the Shapley value of the underlying cooperative game. The proposed algorithm outperforms the existing algorithms in terms of generality or computational complexity or both. Our results are validated through extensive experimentation on both synthetically generated and real-world data sets.

Determining Top K Nodes in Social Networks using the Shapley Value

In this paper, we consider the problem of selecting, for any given positive integer k, the top-k nodes in a social network, based on a certain measure appropriate for the social network. This problem is relevant in many settings such as analysis of co-authorship networks, diffusion of information, viral marketing, etc. However, in most situations, this problem turns out to be NP-hard. The existing approaches for solving this problem are based on approximation algorithms and assume that the objective function is sub-modular. In this paper, we propose a novel and intuitive algorithm based on the Shapley value, for efficiently computing an approximate solution to this problem. Our proposed algorithm does not use the sub-modularity of the underlying objective function and hence it is a general approach. We demonstrate the efficacy of the algorithm using a co-authorship data set from e-print arXiv (www.arxiv.org), having 8361 authors.

Influence limitation in multi-campaign social networks: A Shapley value based approach

We investigate the problem of influence limitation in the presence of competing campaigns in a social network. Given a negative campaign which starts propagating from a specified source and a positive/counter campaign that is initiated, after a certain time delay, to limit the the influence or spread of misinformation by the negative campaign, we are interested in finding the top k influential nodes at which the positive campaign may be triggered. This problem has numerous applications in situations such as limiting the propagation of rumor, arresting the spread of virus through inoculation, initiating a counter-campaign against malicious propaganda, etc. The influence function for the generic influence limitation problem is non-submodular. Restricted versions of the influence limitation problem, reported in the literature, assume submodularity of the influence function and do not capture the problem in a realistic setting. In this paper, we propose a novel computational approach for the influence limitation problem based on Shapley value, a solution concept in cooperative game theory. Our approach works equally effectively for both submodular and non-submodular influence functions. Experiments on standard real world social network datasets reveal that the proposed approach outperforms existing heuristics in the literature. As a non-trivial extension, we also address the problem of influence limitation in the presence of multiple competing campaigns.

Method of designing an access mechanism for social networks

The rapid development of communication and networking has lessened geographical boundaries among actors in social networks. In social networks, actors often want to access databases depending upon their access rights, privacy, context, privileges, etc. Managing and handling knowledge based access of actors is complex and hard for which broad range of technologies need to be called. Access based on dynamic access rights and circumstances of actors impose major tasks on access systems. In this paper, we present an Access Mechanism for Social Networks (AMSN) to render access to actors over databases taking privacy and status of actors into consideration. The designed AMSN model is tested over an Agriculture Social Network (ASN) which utilises distinct access rights and privileges of actors related to the agriculture occupation, and provides access to actors over databases.

Scalable Preference Aggregation in Social Networks

In social choice theory, preference aggregation refers to computing an aggregate preference over a set of alternatives given individual preferences of all the agents. In real-world scenarios, it may not be feasible to gather preferences from all the agents. Moreover, determining the aggregate preference is computationally intensive. In this paper, we show that the aggregate preference of the agents in a social network can be computed efficiently and with sufficient accuracy using preferences elicited from a small subset of critical nodes in the network. Our methodology uses a model developed based on real-world data obtained using a survey on human subjects, and exploits network structure and homophily of relationships. Our approach guarantees good performance for aggregation rules that satisfy a property which we call expected weak insensitivity. We demonstrate empirically that many practically relevant aggregation rules satisfy this property. We also show that two natural objective functions in this context satisfy certain properties, which makes our methodology attractive for scalable preference aggregation over large scale social networks. We conclude that our approach is superior to random polling while aggregating preferences related to individualistic metrics, whereas random polling is acceptable in the case of social metrics.

Game theoretic, decentralized, local information based algorithm for community detection in social graphs

Motivated by the observation that communities in real world social networks form due to actions of rational individuals in networks, we propose a novel game theory inspired algorithm to determine communities in networks. The algorithm is decentralized and only uses local information at each node. We show the efficacy of the proposed algorithm through extensive experimentation on several real world social network data sets.

A Multi-phase Approach for Improving Information Diffusion in Social Networks

For maximizing influence spread in a social network, given a certain budget on the number of seed nodes, we investigate the effects of selecting and activating the seed nodes in multiple phases. In particular, we formulate an appropriate objective function for two-phase influence maximization under the independent cascade model, investigate its properties, and propose algorithms for determining the seed nodes in the two phases. We also study the problem of determining an optimal budget-split and delay between the two phases.

Accelerating Information Diffusion in Social Networks Under the Susceptible-Infected-Susceptible Epidemic Model

Standard Susceptible-Infected-Susceptible (SIS) epidemic models assume that a message spreads from the infected to the susceptible nodes due to only susceptible-infected epidemic contact. We modify the standard SIS epidemic model to include direct recruitment of susceptible individuals to the infected class at a constant rate (independent of epidemic contacts), to accelerate information spreading in a social network. Such recruitment can be carried out by placing advertisements in the media. We provide a closed form analytical solution for system evolution in the proposed model and use it to study campaigning in two different scenarios. In the first, the net cost function is a linear combination of the reward due to extent of information diffusion and the cost due to application of control. In the second, the campaign budget is fixed. Results reveal the effectiveness of the proposed system in accelerating and improving the extent of information diffusion. Our work is useful for devising effective strategies for product marketing and political/social-awareness/crowd-funding campaigns that target individuals in a social network.

Campaigning in Heterogeneous Social Networks: Optimal Control of SI Information Epidemics

We study the optimal control problem of maximizing the spread of an information epidemic on a social network. Information propagation is modeled as a susceptible-infected (SI) process, and the campaign budget is fixed. Direct recruitment and word-of-mouth incentives are the two strategies to accelerate information spreading (controls). We allow for multiple controls depending on the degree of the nodes/individuals. The solution optimally allocates the scarce resource over the campaign duration and the degree class groups. We study the impact of the degree distribution of the network on the controls and present results for Erdos-Renyi and scale-free networks. Results show that more resource is allocated to high-degree nodes in the case of scale-free networks, but medium-degree nodes in the case of Erdos-Renyi networks. We study the effects of various model parameters on the optimal strategy and quantify the improvement offered by the optimal strategy over the static and bang-bang control strategies. The effect of the time-varying spreading rate on the controls is explored as the interest level of the population in the subject of the campaign may change over time. We show the existence of a solution to the formulated optimal control problem, which has nonlinear isoperimetric constraints, using novel techniques that is general and can be used in other similar optimal control problems. This work may be of interest to political, social awareness, or crowdfunding campaigners and product marketing managers, and with some modifications may be used for mitigating biological epidemics.

Turnout Intention and Social Networks

How can networking affect the turnout in an election? We present a simple model to explain turnout as a result of a dynamic process of formation of the intention to vote within Erdös-Renyi random networks. Citizens have fixed preferences for one of two parties and are embedded in a given social network. They decide whether or not to vote on the basis of the attitude of their immediate contacts. They may simply follow the behavior of the majority (followers) or make an adaptive local calculus of voting (Downsian behavior). So they either have the intention of voting when the majority of their neighbors are willing to vote too, or they vote when they perceive in their social neighborhood that elections are "close". We study the long run average turnout, interpreted as the actual turnout observed in an election. Depending on the combination of values of the two key parameters, the average connectivity and the probability of behaving as a follower or in a Downsian fashion, the system exhibits monostability (zero turnout), bistability (zero turnout and either moderate or high turnout) or tristability (zero, moderate and high turnout). This means, in particular, that for a wide range of values of both parameters, we obtain realistic turnout rates, i.e. between 50% and 90%.

Altruism with Social Roots: An Emerging Literature

Revised: 2007-01.-- Published as an article in: Revista Desarrollo y Sociedad (2006), Semestre II, pp. 245-260.

Prosocial norms and degree heterogeneity in social networks

We provide empirical evidence to support the claims that social diversity promotes prosocial behavior. We elicit a real-life social network and its members’ adherence to a social norm, namely inequity aversion. The data reveal a positive relationship between subjects’ prosociality and several measures of centrality. This result is in line with the theoretical literature that relates the evolution of social norms to the structure of social interactions and argues that central individuals are crucial for the emergence of prosocial behavior.

Rede e apoio social e práticas alimentares de crianças no quarto mês de vida

Cerca de 97% das crianças brasileiras iniciam a amamentação ao peito nas primeiras horas de vida. No entanto, o início do desmame é precoce, ocorrendo nas primeiras semanas ou meses de vida, com a introdução de água, chás, sucos, outros leites e alimentos. Fatores sociais, culturais, psicológicos e econômicos, ligados à mãe e ao bebê, podem estar relacionados a variações das práticas alimentares de crianças nos primeiros meses de vida. O objetivo do trabalho foi investigar a associação entre rede e apoio social e as práticas alimentares de lactentes no quarto mês de vida. Foi feito um estudo seccional inserido em uma coorte prospectiva, tendo como população fonte recém-nascidos acolhidos em Unidades Básicas de Saúde da Secretaria Municipal de Saúde do Rio de Janeiro. Para avaliar as práticas alimentares foi aplicado às mães (n=313) um recordatório 24h adaptado e foram construídos dois indicadores considerando o consumo de alimentos sólidos e da alimentação láctea. Para medir rede social foram feitas perguntas relacionadas ao número de parentes e amigos com quem a mulher pode contar e à participação em atividades sociais em grupo. Para aferir apoio social foi utilizada uma escala utilizada no Medical Outcomes Study (MOS) e adaptada para uso no Brasil. A análise dos dados se baseou em modelos de regressão logística multinomial, estimando-se razões de chance e respectivos intervalos de 95% de confiança para as associações entre as variáveis. Observou-se 16% dos lactentes em aleitamento materno exclusivo (AME), 18,8% em aleitamento materno predominante (AMP), aproximadamente 48% em uso de leite materno associado a outros alimentos e 16,5% em aleitamento artificial. Em relação ao aleitamento complementar, 25,9% consumiam alimentos sólidos e 37,5% alimentos lácteos. Crianças filhas de mães que referiram menor número de parentes com quem contar e com baixo apoio social apresentaram maior chance de estar em aleitamento artificial em relação ao AME, quando comparadas com filhas de mães que referiram poder contar com parentes ou com nível alto de apoio social. O baixo apoio social nas dimensões emocional/informação apresentou associação com AMP. Tendo em vista os achados apresentados, destaca-se a necessidade de integrar os membros da rede social da mulher à atenção pré-natal, ao parto e puerpério de modo que esta rede possa prover o apoio social que atenda as suas necessidades e, assim, contribuir para iniciação e manutenção do AME.

Plan de Social Media Marketing en Euskaltel

El presente estudio es un Plan de Social Media Marketing realizado para la empresa Euskaltel, compañía telefónica líder en el País Vasco. Este plan está elaborado para que se ponga en funcionamiento a partir de Septiembre del 2015. El Plan de Social Media Marketing se concreta en una serie de aspectos que se deben tener en cuenta para la puesta en marcha de una estrategia de integración de redes sociales y acciones de marketing digital por parte de la empresa. Una de las principales características del Plan de Social Media Marketing en comparación con otros planes empresariales es su flexibilidad y su disposición para ser rediseñado incluso al día siguiente de ser implantado

Jogos casuais: comunicação, entretenimento e desenvolvimento sustentável em EcoCity

A complexidade do fenômeno comunicacional desafia estudiosos do campo na atualidade, principalmente no âmbito dos ambientes sociais. O processo de interação mediada, por exemplo, ganhou grandes proporções na virada do século XXI com o advento das Tecnologias de Informação e de Comunicação (TIC). Os suportes tecnológicos eletrônicos ou computacionais passaram a nortear grande parte do entretenimento e da comunicação. Nesse caminho esta pesquisa analisa novas práticas de comunicação na atualidade e aponta como os jogos eletrônicos, ou também chamados games, vêm se conjugando nos processos de mediação nessas práticas. O trabalho envolve os jogos para computador, mais especificamente os chamados jogos casuais. O objeto de estudo são os tipos de interação social em jogos casuais online e o corpus de análise é o EcoCity, um jogo de simulação com final aberto que funciona nos sites de serviço de rede social. A abordagem da construção de cidades sustentáveis no game traz fatores ambientais à cena. A hipótese é que a socialização em torno desses fatores podem de alguma forma agregar valor nos usos e apropriações que os indivíduos fazem dos jogos casuais durante os processos comunicativos e interativos.