Papers
Follow
Find
169.0K views | +10 today
Papers
Recent publications related to complex systems
Your new post is loading...
Your new post is loading...
Scooped by Complexity Digest
Scoop.it!

What the No Free Lunch Theorems Really Mean; How to Improve Search Algorithms

The NFL theorems have stimulated lots of subsequent work, with over 2500 citations of [12] alone by spring 2012 according to Google Scholar. However, arguably much of that research has missed the most important implications of the theorems. As stated in [12], the primary importance of the NFL theorems for search is what they tell us about “the underlying mathematical ‘skeleton’ of optimization theory before the ‘flesh’ of the probability distributions of a particular context and set of optimization problems are imposed”. So in particular, while the NFL theorems have strong implications if one believes in a uniform distribution over optimization problems, in no sense should they be interpreted as advocating such a distribution. In this short note I elaborate this perspective on what it is that is really important about the NFL theorems for search. I then discuss how the fact that there are NFL theorems for both search and for supervised learning is symptomatic of the deep formal relationship between those two fields. Once that relationship is disentangled, it suggests many ways that we can exploit practical techniques that were first developed in supervised learning to help us do search. I summarize some experiments that confirm the power of search algorithms developed in this way. I end by briefly discussing the various free lunch theorems that have been derived, and possible directions for future research.

 

Title: What the No Free Lunch Theorems Really Mean; How to Improve Search Algorithms
David H. Wolpert

SFI WP 12-10-017

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

On the Foundations of the Theory of Evolution

Darwinism conceives evolution as a consequence of random variation and natural selection, hence it is based on a materialistic, i.e. matter-based, view of science inspired by classical physics. But matter in itself is considered a very complex notion in modern physics. More specifically, at a microscopic level, matter and energy are no longer retained within their simple form, and quantum mechanical models are proposed wherein potential form is considered in addition to actual form. In this paper we propose an alternative to standard Neodarwinian evolution theory. We suggest that the starting point of evolution theory cannot be limited to actual variation whereupon is selected, but to variation in the potential of entities according to the context. We therefore develop a formalism, referred to as Context driven Actualization of Potential (CAP), which handles potentiality and describes the evolution of entities as an actualization of potential through a reiterated interaction with the context.

 

On the Foundations of the Theory of Evolution

Diederik Aerts, Stan Bundervoet, Marek Czachor, Bart D'Hooghe, Liane Gabora, Philip Polk, Sandro Sozzo

http://arxiv.org/abs/1212.0107

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Collaboratively built semi-structured content and Artificial Intelligence: The story so far

Recent years have seen a great deal of work that exploits collaborative, semi-structured content for Artificial Intelligence (AI) and Natural Language Processing (NLP). This special issue of the Artificial Intelligence Journal presents a variety of state-of-the-art contributions, each of which illustrates the substantial impact that work on leveraging semi-structured content is having on AI and NLP as it continuously fosters new directions of cutting-edge research. We contextualize the papers collected in this special issue by providing a detailed overview of previous work on collaborative, semi-structured resources. The survey is made up of two main logical parts: in the first part, we present the main characteristics of collaborative resources that make them attractive for AI and NLP research; in the second part, we present an overview of how these features have been exploited to tackle a variety of long-standing issues in the two fields, in particular the acquisition of large amounts of machine-readable knowledge, and its application to a wide range of tasks. The overall picture shows that not only are semi-structured resources enabling a renaissance of knowledge-rich AI techniques, but also that significant advances in high-end applications that require deep understanding capabilities can be achieved by synergistically exploiting large amounts of machine-readable structured knowledge in combination with sound statistical AI and NLP techniques.

 

Collaboratively built semi-structured content and Artificial Intelligence: The story so far
Eduard Hovy, Roberto Navigli, , Simone Paolo Ponzetto

Artificial Intelligence
Volume 194, January 2013, Pages 2–27

http://dx.doi.org/10.1016/j.artint.2012.10.002

more...
No comment yet.
Suggested by nperony
Scoop.it!

How Random Is Social Behaviour? Disentangling Social Complexity through the Study of a Wild House Mouse Population

How Random Is Social Behaviour? Disentangling Social Complexity through the Study of a Wild House Mouse Population | Papers | Scoop.it

From the synchronised beauty of fish schools to the rigorous hierarchy of ant colonies, animals often display awe-inspiring collective behaviour. In recent years, principles of statistical physics have helped to unveil some simple mechanisms behind the emergence of such collective dynamics. Among the most elementary tools used to explain group behaviour are random processes, a typical example being the so-called “random walk”. In this paper, we have developed a framework based on such random assumptions to study the spatial and social structure of a population of wild house mice. We introduce the concept of perceptual landscape to describe the spatial behaviour of animals, whilst including all sensory and social constraints they are subject to: the perceptual landscape effectively maps the environment of animals as they perceive it. By applying our assumptions to a multi-agent model, we are able to reveal that much of the high-level social behaviour observed in the mouse population can indeed be explained through the many interactions of randomly moving individuals. This raises the question of how much of what we often regard as complex natural phenomena may, in fact, be the result of exceedingly simple forces.

 

Perony N, Tessone CJ, König B, Schweitzer F (2012) How Random Is Social Behaviour? Disentangling Social Complexity through the Study of a Wild House Mouse Population. PLoS Comput Biol 8(11): e1002786. http://dx.doi.org/10.1371/journal.pcbi.1002786

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Universities Scale Like Cities

Recent studies of urban scaling show that important socioeconomic city characteristics such as wealth and innovation capacity exhibit a nonlinear, particularly a power law scaling with population size. These nonlinear effects are common to all cities, with similar power law exponents. These findings mean that the larger the city, the more disproportionally they are places of wealth and innovation. Local properties of cities cause a deviation from the expected behavior as predicted by the power law scaling. In this paper we demonstrate that universities show a similar behavior as cities in the distribution of the gross university income in terms of total number of citations over size in terms of total number of publications. Moreover, the power law exponents for university scaling are comparable to those for urban scaling.

 

Universities Scale Like Cities

Anthony F. J. van Raan

http://arxiv.org/abs/1211.5124

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Spontaneous motion in hierarchically assembled active matter

Spontaneous motion in hierarchically assembled active matter | Papers | Scoop.it

With remarkable precision and reproducibility, cells orchestrate the cooperative action of thousands of nanometre-sized molecular motors to carry out mechanical tasks at much larger length scales, such as cell motility, division and replication. Besides their biological importance, such inherently non-equilibrium processes suggest approaches for developing biomimetic active materials from microscopic components that consume energy to generate continuous motion. Being actively driven, these materials are not constrained by the laws of equilibrium statistical mechanics and can thus exhibit sought-after properties such as autonomous motility, internally generated flows and self-organized beating. 

 

Spontaneous motion in hierarchically assembled active matter

Tim Sanchez, Daniel T. N. Chen, Stephen J. DeCamp, Michael Heymann & Zvonimir Dogic

Nature 491, 431–434 (15 November 2012)

http://dx.doi.org/10.1038/nature11591

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Dynamical Diagnosis and Solutions for Resilient Natural and Social Systems

The concept of resilience embodies the quest towards the ability to sustain shocks, to suffer from these shocks as little as possible, for the shortest time possible, and to recover with the full functionalities that existed before the perturbation. We propose an operation definition of resilience, seeing it as a measure of stress that is complementary to the risk measures. Emphasis is put on the distinction between stressors (the forces acting on the system) and stress (the internal reaction of the system to the stressors). This allows us to elaborate a classification of stress measures and of the possible responses to stressors.

 

Dynamical Diagnosis and Solutions for Resilient Natural and Social Systems

Tatyana Kovalenko, Didier Sornette

http://arxiv.org/abs/1211.1949

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Long-range navigation on complex networks using Lévy random walks

We introduce a strategy of navigation in undirected networks, including regular, random, and complex networks, that is inspired by Lévy random walks, generalizing previous navigation rules. We obtained exact expressions for the stationary probability distribution, the occupation probability, the mean first passage time, and the average time to reach a node on the network. We found that the long-range navigation using the Lévy random walk strategy, compared with the normal random walk strategy, is more efficient at reducing the time to cover the network. The dynamical effect of using the Lévy walk strategy is to transform a large-world network into a small world. Our exact results provide a general framework that connects two important fields: Lévy navigation strategies and dynamics on complex networks.

 

Long-range navigation on complex networks using Lévy random walks

A. P. Riascos and José L. Mateos

Phys. Rev. E 86, 056110

http://link.aps.org/doi/10.1103/PhysRevE.86.056110

more...
No comment yet.
Rescooped by Complexity Digest from Amazing Science
Scoop.it!

Single-celled amoebae can remember, make decisions and anticipate change - slime molds redefine intelligence

Single-celled amoebae can remember, make decisions and anticipate change - slime molds redefine intelligence | Papers | Scoop.it

Something scientists have come to understand is that slime molds are much smarter than they look. One species in particular, the SpongeBob SquarePants–yellow Physarum polycephalum, can solve mazes, mimic the layout of man-made transportation networks and choose the healthiest food from a diverse menu—and all this without a brain or nervous system. "Slime molds are redefining what you need to have to qualify as intelligent," Reid says.


Via Dr. Stefan Gruenwald
more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

The Biological Origin of Linguistic Diversity

In contrast with animal communication systems, diversity is characteristic of almost every aspect of human language. Languages variously employ tones, clicks, or manual signs to signal differences in meaning; some languages lack the noun-verb distinction (e.g., Straits Salish), whereas others have a proliferation of fine-grained syntactic categories (e.g., Tzeltal); and some languages do without morphology (e.g., Mandarin), while others pack a whole sentence into a single word (e.g., Cayuga). A challenge for evolutionary biology is to reconcile the diversity of languages with the high degree of biological uniformity of their speakers. Here, we model processes of language change and geographical dispersion and find a consistent pressure for flexible learning, irrespective of the language being spoken. This pressure arises because flexible learners can best cope with the observed high rates of linguistic change associated with divergent cultural evolution following human migration. Thus, rather than genetic adaptations for specific aspects of language, such as recursion, the coevolution of genes and fast-changing linguistic structure provides the biological basis for linguistic diversity. Only biological adaptations for flexible learning combined with cultural evolution can explain how each child has the potential to learn any human language.

 

Baronchelli A, Chater N, Pastor-Satorras R, Christiansen MH (2012) The Biological Origin of Linguistic Diversity. PLoS ONE 7(10): e48029. http://dx.doi.org/10.1371/journal.pone.0048029

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Social Relationships and the Emergence of Social Networks

In complex social systems such as those of many mammals, including humans, groups (and hence ego-centric social networks) are commonly structured in discrete layers. We describe a computational model for the development of social relationships based on agents' strategies for social interaction that favour more less-intense, or fewer more-intense partners. A trust-related process controls the formation and decay of relationships as a function of interaction frequency, the history of interaction, and the agents' strategies. A good fit of the observed layers of human social networks was found across a range of model parameter settings. Social interaction strategies which favour interacting with existing strong ties or a time-variant strategy produced more observation-conformant results than strategies favouring more weak relationships. Strong-tie strategies spread in populations under a range of fitness conditions favouring wellbeing, whereas weak-tie strategies spread when fitness favours foraging for food. The implications for modelling the emergence of social relationships in complex structured social networks are discussed.

 

Alistair Sutcliffe, Di Wang and Robin Dunbar (2012)

Social Relationships and the Emergence of Social Networks

Journal of Artificial Societies and Social Simulation 15 (4) 3
http://jasss.soc.surrey.ac.uk/15/4/3.html

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Spatiotemporal correlations of handset-based service usages

We study spatiotemporal correlations and temporal diversities of handset-based service usages by analyzing a dataset that includes detailed information about locations and service usages of 124 users over 16 months. By constructing the spatiotemporal trajectories of the users we detect several meaningful places or contexts for each one of them and show how the context affects the service usage patterns. We find that temporal patterns of service usages are bound to the typical weekly cycles of humans, yet they show maximal activities at different times. We first discuss their temporal correlations and then investigate the time-ordering behavior of communication services like calls being followed by the non-communication services like applications. We also find that the behavioral overlap network based on the clustering of temporal patterns is comparable to the communication network of users. Our approach provides a useful framework for handset-based data analysis and helps us to understand the complexities of information and communications technology enabled human behavior.

 

Spatiotemporal correlations of handset-based service usages
Hang-Hyun Jo, Márton Karsai, Juuso Karikoski and Kimmo Kaski

EPJ Data Science 2012, 1:10 http://dx.doi.org/10.1140/epjds10

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Evolution of Associative Learning in Chemical Networks

Whilst one may have believed that associative learning requires a nervous system, this paper shows that chemical networks can be evolved in silico to undertake a range of associative learning tasks with only a small number of reactions. The mechanisms are surprisingly simple. The networks can be analysed using Bayesian methods to identify the components of the network responsible for learning. The networks evolved were simpler in some ways to hand-designed synthetic biology networks for associative learning. The motifs may be looked for in biochemical networks and the hypothesis that they undertake associative learning, e.g. in single cells or during development may be legitimately entertained.

 

McGregor S, Vasas V, Husbands P, Fernando C (2012) Evolution of Associative Learning in Chemical Networks. PLoS Comput Biol 8(11): e1002739. http://dx.doi.org/10.1371/journal.pcbi.1002739

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Contesting the “Nature” Of Conformity: What Milgram and Zimbardo's Studies Really Show

Understanding of the psychology of tyranny is dominated by classic studies from the 1960s and 1970s: Milgram's research on obedience to authority and Zimbardo's Stanford Prison Experiment. Supporting popular notions of the banality of evil, this research has been taken to show that people conform passively and unthinkingly to both the instructions and the roles that authorities provide, however malevolent these may be. Recently, though, this consensus has been challenged by empirical work informed by social identity theorizing. This suggests that individuals' willingness to follow authorities is conditional on identification with the authority in question and an associated belief that the authority is right.

 

Haslam SA, Reicher SD (2012) Contesting the “Nature” Of Conformity: What Milgram and Zimbardo's Studies Really Show. PLoS Biol 10(11): e1001426. http://dx.doi.org/10.1371/journal.pbio.1001426

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

The Origins of Scaling in Cities

Cities are perhaps the ultimate expression of human sociality displaying at once humanity’s greatest achievements and some of its most difficult challenges. Despite the increasing importance of cities in human societies our ability to understand them scientifically, and manage them in practice, has remained unsatisfactorily limited. The greatest difficulties to any scientific approach to cities have resulted from their many interdependent facets, as social, economic, infrastructural and spatial complex systems, which exist in similar but changing forms over a huge range of scales. Here, I show how cities may evolve following a small set of basic principles that operate locally and can explain how cities change gradually from the bottom-up. As a result I obtain a theoretical framework that derives the general open-ended properties of cities through the optimization of a set of local conditions. This framework is used to predict, in a unified and quantitative way, the average social, spatial and infrastructural properties of cities as a set of scaling relations that apply to all urban systems, many of which have been observed in nations around the world. Finally, I compare and contrast the structure and dynamics of cities to those of other complex systems that share some analogous properties.

 

The Origins of Scaling in Cities
Lúis M. A. Bettencourt

SFI-WP 12-09-014

more...
No comment yet.
Rescooped by Complexity Digest from cognition
Scoop.it!

Reasoning Is Sharper in a Foreign Language

Reasoning Is Sharper in a Foreign Language | Papers | Scoop.it
We might be least rational about money in our native tongues...

 

“When people use a foreign language, their decisions tend to be less biased, more analytic, more systematic, because the foreign language provides psychological distance,”


Via FastTFriend
more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

The Dynamics of Nestedness Predicts the Evolution of Industrial Ecosystems

In economic systems, the mix of products that countries make or export has been shown to be a strong leading indicator of economic growth. Hence, methods to characterize and predict the structure of the network connecting countries to the products that they export are relevant for understanding the dynamics of economic development. Here we study the presence and absence of industries in international and domestic economies and show that these networks are significantly nested.

 

Bustos S, Gomez C, Hausmann R, Hidalgo CA (2012) The Dynamics of Nestedness Predicts the Evolution of Industrial Ecosystems. PLoS One 7(11): e49393. http://dx.doi.org/10.1371/journal.pone.0049393

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Metabolism and disease

Metabolism and disease | Papers | Scoop.it

Abnormal metabolism is at the heart of some serious health problems (such as obesity, diabetes and cancer), which not only reduce our life expectancy, but are also a great cost to society. This Insight offers a snapshot of the molecular mechanisms that underlie metabolism and its associated pathology, and showcases the progress made in this buoyant area of research.

 

Metabolism and disease

Joshua Finkelstein, Noah Gray, Marie Thérèse Heemels, Barbara Marte & Deepa Nath
Nature 491, 347 (15 November 2012)

http://dx.doi.org/10.1038/491347a

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

STIGMERGIC LANDMARK OPTIMIZATION

In this paper we present three Swarm Intelligence algorithms which we evaluate on the complex foraging task domain. Each of the algorithms draws inspiration from biologic bee foraging/nest-site selection behavior. The main focus will be on the third algorithm, namely STIGMERGIC LANDMARK FORAGING which is a novel hybrid approach. It combines the high performance of bee-inspired navigation with ant-inspired recruitment. More precisely, navigation is based on Path Integration which results in vectors indicating the distance and direction to a destination. Recruitment only occurs at key locations (i.e., landmarks) inside of the environment. Each landmark contains a collection of vectors with which visiting agents can find their way to a certain goal or to another landmark in an unknown environment. Each vector represents a local segment of a global route. In contrast to ant-inspired recruitment, no attracting or repelling pheromone is used to indicate where to go and how worthwhile a route is in comparison to other routes. Instead, each vector in a landmark has a certain strength indicating how worthwhile it is. In analogy to ant-inspired recruitment, vector strength can be reinforced by visiting agents. Moreover, vector strength decays over time. In the end, this results in optimal routes to destinations. STIGMERGIC LANDMARK FORAGING proves to be very efficient in terms of building and adapting solutions.

 

STIGMERGIC LANDMARK OPTIMIZATION

N. LEMMENS and K. TUYLS, Advs. Complex Syst. 15, 1150025 (2012)

http://dx.doi.org/10.1142/S0219525911500251

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Bio-Inspired Political Systems. Opening a Field

In this paper we highlight the scopes of engineering bio-inspired political systems, which are political systems based on the properties of life that self-organize the increasing complexity of human social systems. We describe bio-inspired political systems and conjecture about various ways to get to them, most notably, metaheuristics, modeling and simulation and complexified topologies. Bio-inspired political systems operate with nature-based dynamics, inspired on the knowledge that has been acquired about complexity from natural social systems and life. Bio-inspired political systems are presented as the best alternative for organizing human sociopolitical interactions as computation and microelectronics-based technology profoundly modify the ways in which humans decide. Therefore, weakening classical political systems. For instance, dwindling top-down power structures, modifying the notion of geographical spatiality and augmenting the political granularity. We also argue that, more than a new theoretical proposal, bio-inspired political systems are coming to be the political systems of the future.

 

Bio-Inspired Political Systems. Opening a Field

Nathalie Mezza-Garcia

http://arxiv.org/abs/1211.2787

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

FuturICT

FuturlCT is a FET Flagship project using collective, participatory research, integrated across ICT, the social sciences and complexity science, to design socio-inspired technology and develop a science of global, socially interactive systems. The project will bring together, on a global level, Big Data, new modelling techniques and new forms of interaction, leading to a new understanding of society and its coevolution with technology. It aims to understand, explore and manage our complex, connected world in a more sustainable and resilient way. FuturICT is motivated by the fact that ubiquitous communication and sensing blur the boundaries between the physical and digital worlds, creating unparalleled opportunities for understanding the socio-economic fabric of our world, and for empowering humanity to make informed, responsible decisions for its future. The intimate, complex and dynamic relationship between global, networked ICT systems and human society directly influences the complexity and manageability of both. This also opens up the possibility to fundamentally change the way ICT will be designed, built and operated, to reflect the need for socially interactive, ethically sensitive, trustworthy, self-organised and reliable systems. FuturICT will create a new public resource - value-oriented tools and models to aggregate, access, query and understand vast amounts of data. Information from open sources, real-time devices and mobile sensors will be integrated with multi-scale models of the behaviour of social, technological, environmental and economic systems, which can be interrogated by policy-makers, business people and citizens alike. Together, these will build an eco-system that will lead to new business models, scientific paradigm shifts and more rapid and effective ways to create and disseminate new knowledge and social benefits - thereby forming an innovation accelerator.

 

FuturICT

Dirk Helbing, Steven Bishop, Paul Lukowicz, the FuturICT Consortium

http://arxiv.org/abs/1211.2313

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

On the necessity of complexity

Wolfram's Principle of Computational Equivalence (PCE) implies that universal complexity abounds in nature. This paper comprises three sections. In the first section we consider the question why there are so many universal phenomena around. So, in a sense, we week a driving force behind the PCE if any. We postulate a principle GNS that we call the Generalized Natural Selection Principle that together with the Church-Turing Thesis is seen to be equivalent to a weak version of PCE. In the second section we ask the question why we do not observe any phenomena that are complex but not-universal. We choose a cognitive setting to embark on this question and make some analogies with formal logic. In the third and final section we report on a case study where we see rich structures arise everywhere.

 

On the necessity of complexity

Joost J. Joosten

http://arxiv.org/abs/1211.1878

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

How the Scientific Community Reacts to Newly Submitted Preprints: Article Downloads, Twitter Mentions, and Citations

We analyze the online response to the preprint publication of a cohort of 4,606 scientific articles submitted to the preprint database arXiv.org between October 2010 and May 2011. We study three forms of responses to these preprints: downloads on the arXiv.org site, mentions on the social media site Twitter, and early citations in the scholarly record. We perform two analyses. First, we analyze the delay and time span of article downloads and Twitter mentions following submission, to understand the temporal configuration of these reactions and whether one precedes or follows the other. Second, we run regression and correlation tests to investigate the relationship between Twitter mentions, arXiv downloads, and article citations. We find that Twitter mentions and arXiv downloads of scholarly articles follow two distinct temporal patterns of activity, with Twitter mentions having shorter delays and narrower time spans than arXiv downloads. We also find that the volume of Twitter mentions is statistically correlated with arXiv downloads and early citations just months after the publication of a preprint, with a possible bias that favors highly mentioned articles.

 

Shuai X, Pepe A, Bollen J (2012) How the Scientific Community Reacts to Newly Submitted Preprints: Article Downloads, Twitter Mentions, and Citations. PLoS ONE 7(11): e47523. http://dx.doi.org/10.1371/journal.pone.0047523

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

Getting to the Root of Aging

As people live longer, the question arises of how malleable aging is and whether it can be slowed or postponed. The classic evolutionary theories of aging (1–4) provide the theoretical framework that has guided aging research for 60 years. Are the theories consistent with recent evidence?

 

Getting to the Root of Aging
Annette Baudisch, James W. Vaupel

Science 2 November 2012:
Vol. 338 no. 6107 pp. 618-619
http://dx.doi.org/10.1126/science.1226467

more...
No comment yet.
Scooped by Complexity Digest
Scoop.it!

A large-scale community structure analysis in Facebook

Understanding social dynamics that govern human phenomena, such as communications and social relationships is a major problem in current computational social sciences. In particular, given the unprecedented success of online social networks (OSNs), in this paper we are concerned with the analysis of aggregation patterns and social dynamics occurring among users of the largest OSN as the date: Facebook. In detail, we discuss the mesoscopic features of the community structure of this network, considering the perspective of the communities, which has not yet been studied on such a large scale. To this purpose, we acquired a sample of this network containing millions of users and their social relationships; then, we unveiled the communities representing the aggregation units among which users gather and interact; finally, we analyzed the statistical features of such a network of communities, discovering and characterizing some specific organization patterns followed by individuals interacting in online social networks, that emerge considering different sampling techniques and clustering methodologies. This study provides some clues of the tendency of individuals to establish social interactions in online social networks that eventually contribute to building a well-connected social structure, and opens space for further social studies.

 

A large-scale community structure analysis in Facebook
Emilio Ferrara

EPJ Data Science 2012, 1:9 http://dx.doi.org/10.1140/epjds9

more...
luiy's curator insight, March 24, 2013 3:40 PM
Conclusions

The aim of this work was to investigate the emergence of social dynamics, organization patterns and mesoscopic features in the community structure of a large online social network such as Facebook. This task was quite thrilling and not trivial, since a number of theoretical and computational challenges raised.

First of all, we collected real-world data directly from the online network. In fact, as recently put into evidence in literature [40], the differences between synthetic and real-world data have profound implications on results.

After we reconstructed a sample of the structure of the social graph of Facebook, we unveiled its community structure. The main findings that emerged from the mesoscopic analysis of the community structure of this network can be summarized as follows:

(i) We assessed the tendency of online social network users to constitute communities of small size, proving the presence of a decreasing number of communities of larger size. This behavior explains the tendency of users to self-organization even in absence of a coordinated effort.

(ii) We investigated the occurrence of connections among communities, finding that some kind of links, commonly referred as to weak ties, are more relevant than others because they connect communities each other, according to the Granovetter’s strength of weak ties theory[24] and in agreement with recent studies on other online social networks such as Twitter [21].

(iii) The community structure is highly clusterized and the diameter of the community structure meta-network is small (approximately around 4 and 5). These aspects indicate the presence of thesmall world phenomenon, which characterizes real-world social networks, according to sociological studies envisioned by Milgram [23] and in agreement with some heuristic evaluations recently provided by Facebook [18,19].

The achieved results open space for further studies in different directions. As far as it concerns our long-term future research directions, we plan to investigate, amongst others, the following issues:

(i) Devising a model to identify the most representative users inside each given community. This would leave space for further interesting applications, such as the maximization of advertising on online social networks, the analysis of communication dynamics, spread of influence and information and so on.

(ii) Exploiting geographical data regarding the physical location of users of Facebook, to study the effect of strong and weak ties in the society [24]. In fact, is it known that a relevant additional source of information is represented by the geographical distribution of individuals [68-70]. For example, we suppose that strong ties could reflect relations characterized by physical closeness, while weak ties could be more appropriate to represent connections among physically distant individuals.

(iii) Concluding, we devised a strategy to estimate the strength of ties between social network users [71] and we want to study its application to online social networks on a large scale. In the case of social ties, this is equivalent to estimate the friendship degree between a pair of users by considering their interactions and their attitude to exchange information.