BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Manuel Cebrian

Manuel Cebrian appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Social and Information Networksphysics.soc-phcs.CYNeural and Evolutionary ComputingComputer Science and Game TheoryComputer VisionInformation Theorymath.ITPopulations and EvolutionArtificial IntelligenceComputation and LanguageComputational Engineering, Finance, and Scienceeess.IVInformation RetrievalMachine Learningnlin.AOSymbolic Computation

Catalog footprint

What is connected

32works
17topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

32 published item(s)

preprint2021arXiv

Contact Tracing: Computational Bounds, Limitations and Implications

Contact tracing has been extensively studied from different perspectives in recent years. However, there is no clear indication of why this intervention has proven effective in some epidemics (SARS) and mostly ineffective in some others (COVID-19). Here, we perform an exhaustive evaluation of random testing and contact tracing on novel superspreading random networks to try to identify which epidemics are more containable with such measures. We also explore the suitability of positive rates as a proxy of the actual infection statuses of the population. Moreover, we propose novel ideal strategies to explore the potential limits of both testing and tracing strategies. Our study counsels caution, both at assuming epidemic containment and at inferring the actual epidemic progress, with current testing or tracing strategies. However, it also brings a ray of light for the future, with the promise of the potential of novel testing strategies that can achieve great effectiveness.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Social Diffusion Sources Can Escape Detection

Influencing (and being influenced by) others through social networks is fundamental to all human societies. Whether this happens through the diffusion of rumors, opinions, or viruses, identifying the diffusion source (i.e., the person that initiated it) is a problem that has attracted much research interest. Nevertheless, existing literature has ignored the possibility that the source might strategically modify the network structure (by rewiring links or introducing fake nodes) to escape detection. Here, without restricting our analysis to any particular diffusion scenario, we close this gap by evaluating two mechanisms that hide the source-one stemming from the source's actions, the other from the network structure itself. This reveals that sources can easily escape detection, and that removing links is far more effective than introducing fake nodes. Thus, efforts should focus on exposing concealed ties rather than planted entities; such exposure would drastically improve our chances of detecting the diffusion source.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Impossible by Conventional Means: Ten Years on from the DARPA Red Balloon Challenge

Ten years ago, DARPA launched the 'Network Challenge', more commonly known as the 'DARPA Red Balloon Challenge'. Ten red weather balloons were fixed at unknown locations in the US. An open challenge was launched to locate all ten, the first to do so would be declared the winner receiving a cash prize. A team from MIT Media Lab was able to locate them all within 9 hours using social media and a novel reward scheme that rewarded viral recruitment. This achievement was rightly seen as proof of the remarkable ability of social media, then relatively nascent, to solve real world problems such as large-scale spatial search. Upon reflection, however, the challenge was also remarkable as it succeeded despite many efforts to provide false information on the location of the balloons. At the time the false reports were filtered based on manual inspection of visual proof and comparing the IP addresses of those reporting with the purported coordinates of the balloons. In the ten years since, misinformation on social media has grown in prevalence and sophistication to be one of the defining social issues of our time. Seen differently we can cast the misinformation observed in the Red Balloon Challenge, and unexpected adverse effects in other social mobilisation challenges subsequently, not as bugs but as essential features. We further investigate the role of the increasing levels of political polarisation in modulating social mobilisation. We confirm that polarisation not only impedes the overall success of mobilisation, but also leads to a low reachability to oppositely polarised states, significantly hampering recruitment. We find that diversifying geographic pathways of social influence are key to circumvent barriers of political mobilisation and can boost the success of new open challenges.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Algorithmic Discrimination: Formulation and Exploration in Deep Learning-based Face Biometrics

The most popular face recognition benchmarks assume a distribution of subjects without much attention to their demographic attributes. In this work, we perform a comprehensive discrimination-aware experimentation of deep learning-based face recognition. The main aim of this study is focused on a better understanding of the feature space generated by deep models, and the performance achieved over different demographic groups. We also propose a general formulation of algorithmic discrimination with application to face biometrics. The experiments are conducted over the new DiveFace database composed of 24K identities from six different demographic groups. Two popular face recognition models are considered in the experimental framework: ResNet-50 and VGG-Face. We experimentally show that demographic groups highly represented in popular face databases have led to popular pre-trained deep face models presenting strong algorithmic discrimination. That discrimination can be observed both qualitatively at the feature space of the deep models and quantitatively in large performance differences when applying those models in different demographic groups, e.g. for face biometrics.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Human detection of machine manipulated media

Recent advances in neural networks for content generation enable artificial intelligence (AI) models to generate high-quality media manipulations. Here we report on a randomized experiment designed to study the effect of exposure to media manipulations on over 15,000 individuals' ability to discern machine-manipulated media. We engineer a neural network to plausibly and automatically remove objects from images, and we deploy this neural network online with a randomized experiment where participants can guess which image out of a pair of images has been manipulated. The system provides participants feedback on the accuracy of each guess. In the experiment, we randomize the order in which images are presented, allowing causal identification of the learning curve surrounding participants' ability to detect fake content. We find sizable and robust evidence that individuals learn to detect fake content through exposure to manipulated media when provided iterative feedback on their detection attempts. Over a succession of only ten images, participants increase their rating accuracy by over ten percentage points. Our study provides initial evidence that human ability to detect fake, machine-generated content may increase alongside the prevalence of such media online.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Superintelligence cannot be contained: Lessons from Computability Theory

Superintelligence is a hypothetical agent that possesses intelligence far surpassing that of the brightest and most gifted human minds. In light of recent advances in machine intelligence, a number of scientists, philosophers and technologists have revived the discussion about the potential catastrophic risks entailed by such an entity. In this article, we trace the origins and development of the neo-fear of superintelligence, and some of the major proposals for its containment. We argue that such containment is, in principle, impossible, due to fundamental limits inherent to computing itself. Assuming that a superintelligence will contain a program that includes all the programs that can be executed by a universal Turing machine on input potentially as complex as the state of the world, strict containment requires simulations of such a program, something theoretically (and practically) infeasible.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Evolution of Privacy Loss in Wikipedia

The cumulative effect of collective online participation has an important and adverse impact on individual privacy. As an online system evolves over time, new digital traces of individual behavior may uncover previously hidden statistical links between an individual's past actions and her private traits. To quantify this effect, we analyze the evolution of individual privacy loss by studying the edit history of Wikipedia over 13 years, including more than 117,523 different users performing 188,805,088 edits. We trace each Wikipedia's contributor using apparently harmless features, such as the number of edits performed on predefined broad categories in a given time period (e.g. Mathematics, Culture or Nature). We show that even at this unspecific level of behavior description, it is possible to use off-the-shelf machine learning algorithms to uncover usually undisclosed personal traits, such as gender, religion or education. We provide empirical evidence that the prediction accuracy for almost all private traits consistently improves over time. Surprisingly, the prediction performance for users who stopped editing after a given time still improves. The activities performed by new users seem to have contributed more to this effect than additional activities from existing (but still active) users. Insights from this work should help users, system designers, and policy makers understand and make long-term design choices in online content creation systems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Measuring and Optimizing Cultural Markets

Social influence has been shown to create significant unpredictability in cultural markets, providing one potential explanation why experts routinely fail at predicting commercial success of cultural products. To counteract the difficulty of making accurate predictions, "measure and react" strategies have been advocated but finding a concrete strategy that scales for very large markets has remained elusive so far. Here we propose a "measure and optimize" strategy based on an optimization policy that uses product quality, appeal, and social influence to maximize expected profits in the market at each decision point. Our computational experiments show that our policy leverages social influence to produce significant performance benefits for the market, while our theoretical analysis proves that our policy outperforms in expectation any policy not displaying social information. Our results contrast with earlier work which focused on showing the unpredictability and inequalities created by social influence. Not only do we show for the first time that dynamically showing consumers positive social information under our policy increases the expected performance of the seller in cultural markets. We also show that, in reasonable settings, our policy does not introduce significant unpredictability and identifies "blockbusters". Overall, these results shed new light on the nature of social influence and how it can be leveraged for the benefits of the market.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Nowcasting Disaster Damage

Could social media data aid in disaster response and damage assessment? Countries face both an increasing frequency and intensity of natural disasters due to climate change. And during such events, citizens are turning to social media platforms for disaster-related communication and information. Social media improves situational awareness, facilitates dissemination of emergency information, enables early warning systems, and helps coordinate relief efforts. Additionally, spatiotemporal distribution of disaster-related messages helps with real-time monitoring and assessment of the disaster itself. Here we present a multiscale analysis of Twitter activity before, during, and after Hurricane Sandy. We examine the online response of 50 metropolitan areas of the United States and find a strong relationship between proximity to Sandy's path and hurricane-related social media activity. We show that real and perceived threats -- together with the physical disaster effects -- are directly observable through the intensity and composition of Twitter's message stream. We demonstrate that per-capita Twitter activity strongly correlates with the per-capita economic damage inflicted by the hurricane. Our findings suggest that massive online social networks can be used for rapid assessment ("nowcasting") of damage caused by a large-scale disaster.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Crowdsourcing Dilemma

Crowdsourcing offers unprecedented potential for solving tasks efficiently by tapping into the skills of large groups of people. A salient feature of crowdsourcing---its openness of entry---makes it vulnerable to malicious behavior. Such behavior took place in a number of recent popular crowdsourcing competitions. We provide game-theoretic analysis of a fundamental tradeoff between the potential for increased productivity and the possibility of being set back by malicious behavior. Our results show that in crowdsourcing competitions malicious behavior is the norm, not the anomaly---a result contrary to the conventional wisdom in the area. Counterintuitively, making the attacks more costly does not deter them but leads to a less desirable outcome. These findings have cautionary implications for the design of crowdsourcing competitions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficient detection of contagious outbreaks in massive metropolitan encounter networks

Physical contact remains difficult to trace in large metropolitan networks, though it is a key vehicle for the transmission of contagious outbreaks. Co-presence encounters during daily transit use provide us with a city-scale time-resolved physical contact network, consisting of 1 billion contacts among 3 million transit users. Here, we study the advantage that knowledge of such co-presence structures may provide for early detection of contagious outbreaks. We first examine the "friend sensor" scheme --- a simple, but universal strategy requiring only local information --- and demonstrate that it provides significant early detection of simulated outbreaks. Taking advantage of the full network structure, we then identify advanced "global sensor sets", obtaining substantial early warning times savings over the friends sensor scheme. Individuals with highest number of encounters are the most efficient sensors, with performance comparable to individuals with the highest travel frequency, exploratory behavior and structural centrality. An efficiency balance emerges when testing the dependency on sensor size and evaluating sensor reliability; we find that substantial and reliable lead-time could be attained by monitoring only 0.01% of the population with the highest degree.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Iterated crowdsourcing dilemma game

The Internet has enabled the emergence of collective problem solving, also known as crowdsourcing, as a viable option for solving complex tasks. However, the openness of crowdsourcing presents a challenge because solutions obtained by it can be sabotaged, stolen, and manipulated at a low cost for the attacker. We extend a previously proposed crowdsourcing dilemma game to an iterated game to address this question. We enumerate pure evolutionarily stable strategies within the class of so-called reactive strategies, i.e., those depending on the last action of the opponent. Among the 4096 possible reactive strategies, we find 16 strategies each of which is stable in some parameter regions. Repeated encounters of the players can improve social welfare when the damage inflicted by an attack and the cost of attack are both small. Under the current framework, repeated interactions do not really ameliorate the crowdsourcing dilemma in a majority of the parameter space.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Learning in Repeated Games: Human Versus Machine

While Artificial Intelligence has successfully outperformed humans in complex combinatorial games (such as chess and checkers), humans have retained their supremacy in social interactions that require intuition and adaptation, such as cooperation and coordination games. Despite significant advances in learning algorithms, most algorithms adapt at times scales which are not relevant for interactions with humans, and therefore the advances in AI on this front have remained of a more theoretical nature. This has also hindered the experimental evaluation of how these algorithms perform against humans, as the length of experiments needed to evaluate them is beyond what humans are reasonably expected to endure (max 100 repetitions). This scenario is rapidly changing, as recent algorithms are able to converge to their functional regimes in shorter time-scales. Additionally, this shift opens up possibilities for experimental investigation: where do humans stand compared with these new algorithms? We evaluate humans experimentally against a representative element of these fast-converging algorithms. Our results indicate that the performance of at least one of these algorithms is comparable to, and even exceeds, the performance of people.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Performance of Social Network Sensors During Hurricane Sandy

Information flow during catastrophic events is a critical aspect of disaster management. Modern communication platforms, in particular online social networks, provide an opportunity to study such flow, and a mean to derive early-warning sensors, improving emergency preparedness and response. Performance of the social networks sensor method, based on topological and behavioural properties derived from the "friendship paradox", is studied here for over 50 million Twitter messages posted before, during, and after Hurricane Sandy. We find that differences in user's network centrality effectively translate into moderate awareness advantage (up to 26 hours); and that geo-location of users within or outside of the hurricane-affected area plays significant role in determining the scale of such advantage. Emotional response appears to be universal regardless of the position in the network topology, and displays characteristic, easily detectable patterns, opening a possibility of implementing a simple "sentiment sensing" technique to detect and locate disasters.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantifying long-term evolution of intra-urban spatial interactions

Understanding the long-term impact that changes in a city's transportation infrastructure have on its spatial interactions remains a challenge. The difficulty arises from the fact that the real impact may not be revealed in static or aggregated mobility measures, as these are remarkably robust to perturbations. More generally, the lack of longitudinal, cross-sectional data demonstrating the evolution of spatial interactions at a meaningful urban scale also hinders us from evaluating the sensitivity of movement indicators, limiting our capacity to understand the evolution of urban mobility in depth. Using very large mobility records distributed over three years we quantify the impact of the completion of a metro line extension: the circle line (CCL) in Singapore. We find that the commonly used movement indicators are almost identical before and after the project was completed. However, in comparing the temporal community structure across years, we do observe significant differences in the spatial reorganization of the affected geographical areas. The completion of CCL enables travelers to re-identify their desired destinations collectively with lower transport cost, making the community structure more consistent. These changes in locality are dynamic, and characterized over short time-scales, offering us a different approach to identify and analyze the long-term impact of new infrastructures on cities and their evolution dynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Targeted Social Mobilisation in a Global Manhunt

Social mobilization, the ability to mobilize large numbers of people via social networks to achieve highly distributed tasks, has received significant attention in recent times. This growing capability, facilitated by modern communication technology, is highly relevant to endeavors which require the search for individuals that posses rare information or skill, such as finding medical doctors during disasters, or searching for missing people. An open question remains, as to whether in time-critical situations, people are able to recruit in a targeted manner, or whether they resort to so-called blind search, recruiting as many acquaintances as possible via broadcast communication. To explore this question, we examine data from our recent success in the U.S. State Department's Tag Challenge, which required locating and photographing 5 target persons in 5 different cities in the United States and Europe in less than 12 hours, based only on a single mug-shot. We find that people are able to consistently route information in a targeted fashion even under increasing time pressure. We derive an analytical model for global mobilization and use it to quantify the extent to which people were targeting others during recruitment. Our model estimates that approximately 1 in 3 messages were of targeted fashion during the most time-sensitive period of the challenge.This is a novel observation at such short temporal scales, and calls for opportunities for devising viral incentive schemes that provide distance- or time-sensitive rewards to approach the target geography more rapidly, with applications in multiple areas from emergency preparedness, to political mobilization.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Corruption Drives the Emergence of Civil Society

Peer punishment of free-riders (defectors) is a key mechanism for promoting cooperation in society. However, it is highly unstable since some cooperators may contribute to a common project but refuse to punish defectors. Centralized sanctioning institutions (for example, tax-funded police and criminal courts) can solve this problem by punishing both defectors and cooperators who refuse to punish. These institutions have been shown to emerge naturally through social learning and then displace all other forms of punishment, including peer punishment. However, this result provokes a number of questions. If centralized sanctioning is so successful, then why do many highly authoritarian states suffer from low levels of cooperation? Why do states with high levels of public good provision tend to rely more on citizen-driven peer punishment? And what happens if centralized institutions can be circumvented by individual acts of bribery? Here, we consider how corruption influences the evolution of cooperation and punishment. Our model shows that the effectiveness of centralized punishment in promoting cooperation breaks down when some actors in the model are allowed to bribe centralized authorities. Counterintuitively, increasing the sanctioning power of the central institution makes things even worse, since this prevents peer punishers from playing a role in maintaining cooperation. As a result, a weaker centralized authority is actually more effective because it allows peer punishment to restore cooperation in the presence of corruption. Our results provide an evolutionary rationale for why public goods provision rarely flourishes in polities that rely only on strong centralized institutions. Instead, cooperation requires both decentralized and centralized enforcement. These results help to explain why citizen participation is a fundamental necessity for policing the commons.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Urban characteristics attributable to density-driven tie formation

Motivated by empirical evidence on the interplay between geography, population density and societal interaction, we propose a generative process for the evolution of social structure in cities. Our analytical and simulation results predict both super-linear scaling of social tie density and information flow as a function of the population. We demonstrate that our model provides a robust and accurate fit for the dependency of city characteristics with city size, ranging from individual-level dyadic interactions (number of acquaintances, volume of communication) to population-level variables (contagious disease rates, patenting activity, economic productivity and crime) without the need to appeal to modularity, specialization, or hierarchy.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Experimental study of the impact of historical information in human coordination

We perform laboratory experiments to elucidate the role of historical information in games involving human coordination. Our approach follows prior work studying human network coordination using the task of graph coloring. We first motivate this research by showing empirical evidence that the resolution of coloring conflicts is dependent upon the recent local history of that conflict. We also conduct two tailored experiments to manipulate the game history that can be used by humans in order to determine (i) whether humans use historical information, and (ii) whether they use it effectively. In the first variant, during the course of each coloring task, the network positions of the subjects were periodically swapped while maintaining the global coloring state of the network. In the second variant, participants completed a series of 2-coloring tasks, some of which were restarts from checkpoints of previous tasks. Thus, the participants restarted the coloring task from a point in the middle of a previous task without knowledge of the history that led to that point. We report on the game dynamics and average completion times for the diverse graph topologies used in the swap and restart experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Modeling Dynamical Influence in Human Interaction Patterns

How can we model influence between individuals in a social system, even when the network of interactions is unknown? In this article, we review the literature on the "influence model," which utilizes independent time series to estimate how much the state of one actor affects the state of another actor in the system. We extend this model to incorporate dynamical parameters that allow us to infer how influence changes over time, and we provide three examples of how this model can be applied to simulated and real data. The results show that the model can recover known estimates of influence, it generates results that are consistent with other measures of social networks, and it allows us to uncover important shifts in the way states may be transmitted between actors at different points in time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Weakness of Weak Ties in the Classroom

Granovetter's "strength of weak ties" hypothesizes that isolated social ties offer limited access to external prospects, while heterogeneous social ties diversify one's opportunities. We analyze the most complete record of college student interactions to date (approximately 80,000 interactions by 290 students -- 16 times more interactions with almost 3 times more students than previous studies on educational networks) and compare the social interaction data with the academic scores of the students. Our first finding is that social diversity is negatively correlated with performance. This is explained by our second finding: highly performing students interact in groups of similarly performing peers. This effect is stronger the higher the student performance is. Indeed, low performance students tend to initiate many transient interactions independently of the performance of their target. In other words, low performing students act disassortatively with respect to their social network, whereas high scoring students act assortatively. Our data also reveals that highly performing students establish persistent interactions before mid and low performing ones and that they use more structured and longer cascades of information from which low performing students are excluded.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Using Friends as Sensors to Detect Global-Scale Contagious Outbreaks

Recent research has focused on the monitoring of global-scale online data for improved detection of epidemics, mood patterns, movements in the stock market, political revolutions, box-office revenues, consumer behaviour and many other important phenomena. However, privacy considerations and the sheer scale of data available online are quickly making global monitoring infeasible, and existing methods do not take full advantage of local network structure to identify key nodes for monitoring. Here, we develop a model of the contagious spread of information in a global-scale, publicly-articulated social network and show that a simple method can yield not just early detection, but advance warning of contagious outbreaks. In this method, we randomly choose a small fraction of nodes in the network and then we randomly choose a "friend" of each node to include in a group for local monitoring. Using six months of data from most of the full Twittersphere, we show that this friend group is more central in the network and it helps us to detect viral outbreaks of the use of novel hashtags about 7 days earlier than we could with an equal-sized randomly chosen group. Moreover, the method actually works better than expected due to network structure alone because highly central actors are both more active and exhibit increased diversity in the information they transmit to others. These results suggest that local monitoring is not just more efficient, it is more effective, and it is possible that other contagious processes in global-scale networks may be similarly monitored.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Social Networks and Spin Glasses

The networks formed from the links between telephones observed in a month's call detail records (CDRs) in the UK are analyzed, looking for the characteristics thought to identify a communications network or a social network. Some novel methods are employed. We find similarities to both types of network. We conclude that, just as analogies to spin glasses have proved fruitful for optimization of large scale practical problems, there will be opportunities to exploit a statistical mechanics of the formation and dynamics of social networks in today's electronically connected world.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Thermodynamics of Information Retrieval

In this work, we suggest a parameterized statistical model (the gamma distribution) for the frequency of word occurrences in long strings of English text and use this model to build a corresponding thermodynamic picture by constructing the partition function. We then use our partition function to compute thermodynamic quantities such as the free energy and the specific heat. In this approach, the parameters of the word frequency model vary from word to word so that each word has a different corresponding thermodynamics and we suggest that differences in the specific heat reflect differences in how the words are used in language, differentiating keywords from common and function words. Finally, we apply our thermodynamic picture to the problem of retrieval of texts based on keywords and suggest some advantages over traditional information retrieval methods.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Grammatical Evolution with Restarts for Fast Fractal Generation

In a previous work, the authors proposed a Grammatical Evolution algorithm to automatically generate Lindenmayer Systems which represent fractal curves with a pre-determined fractal dimension. This paper gives strong statistical evidence that the probability distributions of the execution time of that algorithm exhibits a heavy tail with an hyperbolic probability decay for long executions, which explains the erratic performance of different executions of the algorithm. Three different restart strategies have been incorporated in the algorithm to mitigate the problems associated to heavy tail distributions: the first assumes full knowledge of the execution time probability distribution, the second and third assume no knowledge. These strategies exploit the fact that the probability of finding a solution in short executions is non-negligible and yield a severe reduction, both in the expected execution time (up to one order of magnitude) and in its variance, which is reduced from an infinite to a finite value.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Modeling Corporate Epidemiology

Corporate responses to illness is currently an ad-hoc, subjective process that has little basis in data on how disease actually spreads at the workplace. Additionally, many studies have shown that productivity is not an individual factor but a social one: in any study on epidemic responses this social factor has to be taken into account. The barrier to addressing this problem has been the lack of data on the interaction and mobility patterns of people in the workplace. We have created a wearable Sociometric Badge that senses interactions between individuals using an infra-red (IR) transceiver and proximity using a radio transmitter. Using the data from the Sociometric Badges, we are able to simulate diseases spreading through face-to-face interactions with realistic epidemiological parameters. In this paper we construct a curve trading off productivity with epidemic potential. We are able to take into account impacts on productivity that arise from social factors, such as interaction diversity and density, which studies that take an individual approach ignore. We also propose new organizational responses to diseases that take into account behavioral patterns that are associated with a more virulent disease spread. This is advantageous because it will allow companies to decide appropriate responses based on the organizational context of a disease outbreak.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Overcoming Problems in the Measurement of Biological Complexity

In a genetic algorithm, fluctuations of the entropy of a genome over time are interpreted as fluctuations of the information that the genome's organism is storing about its environment, being this reflected in more complex organisms. The computation of this entropy presents technical problems due to the small population sizes used in practice. In this work we propose and test an alternative way of measuring the entropy variation in a population by means of algorithmic information theory, where the entropy variation between two generational steps is the Kolmogorov complexity of the first step conditioned to the second one. As an example application of this technique, we report experimental differences in entropy evolution between systems in which sexual reproduction is present or absent.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Patterns of Individual Shopping Behavior

Much of economic theory is built on observations of aggregate, rather than individual, behavior. Here, we present novel findings on human shopping patterns at the resolution of a single purchase. Our results suggest that much of our seemingly elective activity is actually driven by simple routines. While the interleaving of shopping events creates randomness at the small scale, on the whole consumer behavior is largely predictable. We also examine income-dependent differences in how people shop, and find that wealthy individuals are more likely to bundle shopping trips. These results validate previous work on mobility from cell phone data, while describing the unpredictability of behavior at higher resolution.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stealing Reality

In this paper we discuss the threat of malware targeted at extracting information about the relationships in a real-world social network as well as characteristic information about the individuals in the network, which we dub Stealing Reality. We present Stealing Reality, explain why it differs from traditional types of network attacks, and discuss why its impact is significantly more dangerous than that of other attacks. We also present our initial analysis and results regarding the form that an SR attack might take, with the goal of promoting the discussion of defending against such an attack, or even just detecting the fact that one has already occurred.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Time Critical Social Mobilization: The DARPA Network Challenge Winning Strategy

It is now commonplace to see the Web as a platform that can harness the collective abilities of large numbers of people to accomplish tasks with unprecedented speed, accuracy and scale. To push this idea to its limit, DARPA launched its Network Challenge, which aimed to "explore the roles the Internet and social networking play in the timely communication, wide-area team-building, and urgent mobilization required to solve broad-scope, time-critical problems." The challenge required teams to provide coordinates of ten red weather balloons placed at different locations in the continental United States. This large-scale mobilization required the ability to spread information about the tasks widely and quickly, and to incentivize individuals to act. We report on the winning team's strategy, which utilized a novel recursive incentive mechanism to find all balloons in under nine hours. We analyze the theoretical properties of the mechanism, and present data about its performance in the challenge.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Contextual Information Retrieval based on Algorithmic Information Theory and Statistical Outlier Detection

The main contribution of this paper is to design an Information Retrieval (IR) technique based on Algorithmic Information Theory (using the Normalized Compression Distance- NCD), statistical techniques (outliers), and novel organization of data base structure. The paper shows how they can be integrated to retrieve information from generic databases using long (text-based) queries. Two important problems are analyzed in the paper. On the one hand, how to detect "false positives" when the distance among the documents is very low and there is actual similarity. On the other hand, we propose a way to structure a document database which similarities distance estimation depends on the length of the selected text. Finally, the experimental evaluations that have been carried out to study previous problems are shown.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Exploiting Heavy Tails in Training Times of Multilayer Perceptrons: A Case Study with the UCI Thyroid Disease Database

The random initialization of weights of a multilayer perceptron makes it possible to model its training process as a Las Vegas algorithm, i.e. a randomized algorithm which stops when some required training error is obtained, and whose execution time is a random variable. This modeling is used to perform a case study on a well-known pattern recognition benchmark: the UCI Thyroid Disease Database. Empirical evidence is presented of the training time probability distribution exhibiting a heavy tail behavior, meaning a big probability mass of long executions. This fact is exploited to reduce the training time cost by applying two simple restart strategies. The first assumes full knowledge of the distribution yielding a 40% cut down in expected time with respect to the training without restarts. The second, assumes null knowledge, yielding a reduction ranging from 9% to 23%.

0 citations0 reviewsNo code linkedOpen access