ترغب بنشر مسار تعليمي؟ اضغط هنا

Social Networks with Competing Products

222   0   0.0 ( 0 )
 نشر من قبل Krzysztof R. Apt
 تاريخ النشر 2012
والبحث باللغة English




اسأل ChatGPT حول البحث

We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We characterize social networks for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed. These characterizations directly yield polynomial time algorithms that allow us to determine whether a given social network satisfies one of the above properties. We also study algorithmic questions for networks without unique outcomes. We show that the problem of determining whether a final network exists in which all nodes adopted some product is NP-complete. In turn, the problems of determining whether a given node adopts some (respectively, a given) product in some (respectively, all) network(s) are either co-NP complete or can be solved in polynomial time. Further, we show that the problem of computing the minimum possible spread of a product is NP-hard to approximate with an approximation ratio better than $Omega(n)$, in contrast to the maximum spread, which is efficiently computable. Finally, we clarify that some of the above problems can be solved in polynomial time when there are only two products.



قيم البحث

اقرأ أيضاً

117 - Chen Feng , Jiahui Sun , Luiyi Fu 2021
Influence competition finds its significance in many applications, such as marketing, politics and public events like COVID-19. Existing work tends to believe that the stronger influence will always win and dominate nearly the whole network, i.e., wi nner takes all. However, this finding somewhat contradicts with our common sense that many competing products are actually coexistent, e.g., Android vs. iOS. This contradiction naturally raises the question: will the winner take all? To answer this question, we make a comprehensive study into influence competition by identifying two factors frequently overlooked by prior art: (1) the incomplete observation of real diffusion networks; (2) the existence of information overload and its impact on user behaviors. To this end, we attempt to recover possible diffusion links based on user similarities, which are extracted by embedding users into a latent space. Following this, we further derive the condition under which users will be overloaded, and formulate the competing processes where users behaviors differ before and after information overload. By establishing the explicit expressions of competing dynamics, we disclose that information overload acts as the critical boundary line, before which the winner takes all phenomenon will definitively occur, whereas after information overload the share of influences gradually stabilizes and is jointly affected by their initial spreading conditions, influence powers and the advent of overload. Numerous experiments are conducted to validate our theoretical results where favorable agreement is found. Our work sheds light on the intrinsic driving forces behind real-world dynamics, thus providing useful insights into effective information engineering.
This paper describes the deployment of a large-scale study designed to measure human interactions across a variety of communication channels, with high temporal resolution and spanning multiple years - the Copenhagen Networks Study. Specifically, we collect data on face-to-face interactions, telecommunication, social networks, location, and background information (personality, demographic, health, politics) for a densely connected population of 1,000 individuals, using state-of-art smartphones as social sensors. Here we provide an overview of the related work and describe the motivation and research agenda driving the study. Additionally the paper details the data-types measured, and the technical infrastructure in terms of both backend and phone software, as well as an outline of the deployment procedures. We document the participant privacy procedures and their underlying principles. The paper is concluded with early results from data analysis, illustrating the importance of multi-channel high-resolution approach to data collection.
Random walk-based sampling methods are gaining popularity and importance in characterizing large networks. While powerful, they suffer from the slow mixing problem when the graph is loosely connected, which results in poor estimation accuracy. Random walk with jumps (RWwJ) can address the slow mixing problem but it is inapplicable if the graph does not support uniform vertex sampling (UNI). In this work, we develop methods that can efficiently sample a graph without the necessity of UNI but still enjoy the similar benefits as RWwJ. We observe that many graphs under study, called target graphs, do not exist in isolation. In many situations, a target graph is related to an auxiliary graph and a bipartite graph, and they together form a better connected {em two-layered network structure}. This new viewpoint brings extra benefits to graph sampling: if directly sampling a target graph is difficult, we can sample it indirectly with the assistance of the other two graphs. We propose a series of new graph sampling techniques by exploiting such a two-layered network structure to estimate target graph characteristics. Experiments conducted on both synthetic and real-world networks demonstrate the effectiveness and usefulness of these new techniques.
Here, we review the research we have done on social contagion. We describe the methods we have employed (and the assumptions they have entailed) in order to examine several datasets with complementary strengths and weaknesses, including the Framingha m Heart Study, the National Longitudinal Study of Adolescent Health, and other observational and experimental datasets that we and others have collected. We describe the regularities that led us to propose that human social networks may exhibit a three degrees of influence property, and we review statistical approaches we have used to characterize inter-personal influence with respect to phenomena as diverse as obesity, smoking, cooperation, and happiness. We do not claim that this work is the final word, but we do believe that it provides some novel, informative, and stimulating evidence regarding social contagion in longitudinally followed networks. Along with other scholars, we are working to develop new methods for identifying causal effects using social network data, and we believe that this area is ripe for statistical development as current methods have known and often unavoidable limitations.
We study the problem of optimally investing in nodes of a social network in a competitive setting, wherein two camps aim to drive the average opinion of the population in their own favor. Using a well-established model of opinion dynamics, we formula te the problem as a zero-sum game with its players being the two camps. We derive optimal investment strategies for both camps, and show that a random investment strategy is optimal when the underlying network follows a popular class of weight distributions. We study a broad framework, where we consider various well-motivated settings of the problem, namely, when the influence of a camp on a node is a concave function of its investment on that node, when a camp aims at maximizing competitors investment or deviation from its desired investment, and when one of the camps has uncertain information about the values of the model parameters. We also study a Stackelberg variant of this game under common coupled constraints on the combined investments by the camps and derive their equilibrium strategies, and hence quantify the first-mover advantage. For a quantitative and illustrative study, we conduct simulations on real-world datasets and provide results and insights.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا