In this paper, we investigate the effect of heterogeneity of link weight, heterogeneity of the frequency or amount of interactions among individuals, on the evolution of cooperation. Based on an analysis of the evolutionary prisoners dilemma game on a weighted one-dimensional lattice network with intra-individual heterogeneity, we confirm that moderate level of link-weight heterogeneity can facilitate cooperation. Furthermore, we identify two key mechanisms by which link-weight heterogeneity promotes the evolution of cooperation: mechanisms for spread and maintenance of cooperation. We also derive the corresponding conditions under which the mechanisms can work through evolutionary dynamics.
In this paper we apply techniques of complex network analysis to data sources representing public funding programs and discuss the importance of the considered indicators for program evaluation. Starting from the Open Data repository of the 2007-2013 Italian Program Programma Operativo Nazionale Ricerca e Competitivit`a (PON R&C), we build a set of data models and perform network analysis over them. We discuss the obtained experimental results outlining interesting new perspectives that emerge from the application of the proposed methods to the socio-economical evaluation of funded programs.
Sociological studies on transnational migration are often based on surveys or interviews, an expensive and time consuming approach. On the other hand, the pervasiveness of mobile phones and location aware social networks has introduced new ways to understand human mobility patterns at a national or global scale. In this work, we leverage geo located information obtained from Twitter as to understand transnational migration patterns between two border cities (San Diego, USA and Tijuana, Mexico). We obtained 10.9 million geo located tweets from December 2013 to January 2015. Our method infers human mobility by inspecting tweet submissions and users home locations. Our results depict a trans national community structure that exhibits the formation of a functional metropolitan area that physically transcends international borders. These results show the potential for re analysing sociology phenomena from a technology based empirical perspective.
Great cities connect people; failed cities isolate people. Despite the fundamental importance of physical, face-to-face social-ties in the functioning of cities, these connectivity networks are not explicitly observed in their entirety. Attempts at estimating them often rely on unrealistic over-simplifications such as the assumption of spatial homogeneity. Here we propose a mathematical model of human interactions in terms of a local strategy of maximising the number of beneficial connections attainable under the constraint of limited individual travelling-time budgets. By incorporating census and openly-available online multi-modal transport data, we are able to characterise the connectivity of geometrically and topologically complex cities. Beyond providing a candidate measure of greatness, this model allows one to quantify and assess the impact of transport developments, population growth, and other infrastructure and demographic changes on a city. Supported by validations of GDP and HIV infection rates across United States metropolitan areas, we illustrate the effect of changes in local and city-wide connectivities by considering the economic impact of two contemporary inter- and intra-city transport developments in the United Kingdom: High Speed Rail 2 and London Crossrail. This derivation of the model suggests that the scaling of different urban indicators with population size has an explicitly mechanistic origin.
We propose and develop a Lexicocalorimeter: an online, interactive instrument for measuring the caloric content of social media and other large-scale texts. We do so by constructing extensive yet improvable tables of food and activity related phrases, and respectively assigning them with sourced estimates of caloric intake and expenditure. We show that for Twitter, our naive measures of caloric input, caloric output, and the ratio of these measures are all strong correlates with health and well-being measures for the contiguous United States. Our caloric balance measure in many cases outperforms both its constituent quantities, is tunable to specific health and well-being measures such as diabetes rates, has the capability of providing a real-time signal reflecting a populations health, and has the potential to be used alongside traditional survey data in the development of public policy and collective self-awareness. Because our Lexicocalorimeter is a linear superposition of principled phrase scores, we also show we can move beyond correlations to explore what people talk about in collective detail, and assist in the understanding and explanation of how population-scale conditions vary, a capacity unavailable to black-box type methods.
In spite of the extensive previous efforts on traffic dynamics and epidemic spreading in complex networks, the problem of traffic-driven epidemic spreading on {em correlated} networks has not been addressed. Interestingly, we find that the epidemic threshold, a fundamental quantity underlying the spreading dynamics, exhibits a non-monotonic behavior in that it can be minimized for some critical value of the assortativity coefficient, a parameter characterizing the network correlation. To understand this phenomenon, we use the degree-based mean-field theory to calculate the traffic-driven epidemic threshold for correlated networks. The theory predicts that the threshold is inversely proportional to the packet-generation rate and the largest eigenvalue of the betweenness matrix. We obtain consistency between theory and numerics. Our results may provide insights into the important problem of controlling/harnessing real-world epidemic spreading dynamics driven by traffic flows.
The Adaptive Seeding problem is an algorithmic challenge motivated by influence maximization in social networks: One seeks to select among certain accessible nodes in a network, and then select, adaptively, among neighbors of those nodes as they become accessible in order to maximize a global objective function. More generally, adaptive seeding is a stochastic optimization framework where the choices in the first stage affect the realizations in the second stage, over which we aim to optimize. Our main result is a $(1-1/e)^2$-approximation for the adaptive seeding problem for any monotone submodular function. While adaptive policies are often approximated via non-adaptive policies, our algorithm is based on a novel method we call emph{locally-adaptive} policies. These policies combine a non-adaptive global structure, with local adaptive optimizations. This method enables the $(1-1/e)^2$-approximation for general monotone submodular functions and circumvents some of the impossibilities associated with non-adaptive policies. We also introduce a fundamental problem in submodular optimization that may be of independent interest: given a ground set of elements where every element appears with some small probability, find a set of expected size at most $k$ that has the highest expected value over the realization of the elements. We show a surprising result: there are classes of monotone submodular functions (including coverage) that can be approximated almost optimally as the probability vanishes. For general monotone submodular functions we show via a reduction from textsc{Planted-Clique} that approximations for this problem are not likely to be obtainable. This optimization problem is an important tool for adaptive seeding via non-adaptive policies, and its hardness motivates the introduction of emph{locally-adaptive} policies we use in the main result.
Studies on friendships in online social networks involving geographic distance have so far relied on the city location provided in users profiles. Consequently, most of the research on friendships have provided accuracy at the city level, at best, to designate a users location. This study analyzes a Twitter dataset because it provides the exact geographic distance between corresponding users. We start by introducing a strong definition of friend on Twitter (i.e., a definition of bidirectional friendship), requiring bidirectional communication. Next, we utilize geo-tagged mentions delivered by users to determine their locations, where @username is contained anywhere in the body of tweets. To provide analysis results, we first introduce a friend counting algorithm. From the fact that Twitter users are likely to post consecutive tweets in the static mode, we also introduce a two-stage distance estimation algorithm. As the first of our main contributions, we verify that the number of friends of a particular Twitter user follows a well-known power-law distribution (i.e., a Zipfs distribution or a Pareto distribution). Our study also provides the following newly-discovered friendship degree related to the issue of space: The number of friends according to distance follows a double power-law (i.e., a double Pareto law) distribution, indicating that the probability of befriending a particular Twitter user is significantly reduced beyond a certain geographic distance between users, termed the separation point. Our analysis provides concrete evidence that Twitter can be a useful platform for assigning a more accurate scalar value to the degree of friendship between two users.
It has recently become possible to record detailed social interactions in large social systems with high resolution. As we study these datasets, human social interactions display patterns that emerge at multiple time scales, from minutes to months. On a fundamental level, understanding of the network dynamics can be used to inform the process of measuring social networks. The details of measurement are of particular importance when considering dynamic processes where minute-to-minute details are important, because collection of physical proximity interactions with high temporal resolution is difficult and expensive. Here, we consider the dynamic network of proximity-interactions between approximately 500 individuals participating in the Copenhagen Networks Study. We show that in order to accurately model spreading processes in the network, the dynamic processes that occur on the order of minutes are essential and must be included in the analysis.
In addition to posting news and status updates, many Twitter users post questions that seek various types of subjective and objective information. These questions are often labeled with Q&A hashtags, such as #lazyweb or #twoogle. We surveyed Twitter users and found they employ these Q&A hashtags both as a topical signifier (this tweet needs an answer!) and to reach out to those beyond their immediate followers (a community of helpful tweeters who monitor the hashtag). However, our log analysis of thousands of hashtagged Q&A exchanges reveals that nearly all replies to hashtagged questions come from a users immediate follower network, contradicting users beliefs that they are tapping into a larger community by tagging their question tweets. This finding has implications for designing next-generation social search systems that reach and engage a wide audience of answerers.
