Read our latest paper titled Social Dynamics of Science in Nature Scientific Reports. Authors Xiaoling Sun, Jasleen Kaur, Staša Milojević, Alessandro Flammini & Filippo Menczer ask, How do scientific disciplines emerge? No quantitative model to date allows us to validate competing theories on the different roles of endogenous processes, such as social collaborations, and exogenous events, such as scientific discoveries. Here we propose an agent-based model in which the evolution of disciplines is guided mainly by social interactions among agents representing scientists. Disciplines emerge from splitting and merging of social communities in a collaboration network. We find that this social model can account for a number of stylized facts about the relationships between disciplines, scholars, and publications. These results provide strong quantitative support for the key role of social interactions in shaping the dynamics of science. While several “science of science” theories exist, this is the first account for the emergence of disciplines that is validated on the basis of empirical data.

We are excited to welcome a new faculty member, Yong-Yeol “YY” Ahn, to our center. Prior to joining IU, YY was a postdoctoral researcher at the Center for Complex Network Research at Northeastern University and a visiting researcher at the Center for Cancer Systems Biology at Dana-Farber Cancer Institute, working with Albert-László Barabási. YY has a PhD in Physics from KAIST in Korea. His work explores  the structure and dynamics of complex systems, spanning from molecules to society.

YY has been selected by the Association of Korean Physicists in America as one of the two winners of the annual Outstanding Young Researcher Award. And to top it off, his paper on Flavor network and the principles of food pairing was the most downloaded of all Nature.com in December 2011. Congratulations!

LaNeT-vi, a program that represents large-scale networks in two-dimensions, was used to create the cover image for the November edition of Nature Physics. The featured image highlights several nodes in the foreground that stand out from the rest of the network, highlighting the main thrust of the journal’s cover story; the most efficient spreaders in a network are not necessarily the most connected or central. Instead, efficient spreading correlates with spreader location within the core of the network as determined by the k-shell decomposition analysis.

Determining what makes an efficient spreader in a network is essential for optimizing network efficiency and the deployment of resources. As a publicly-available online tool, LaNeT-vi assists in this effort by allowing users to upload their own networks and receive original renderings of their information based on the k-core decomposition.

LaNeT-vi was developed in-house at the School of Informatics and Computing at Indiana University in collaboration with the CNRS, France and the CONICET in Argentina.

Back to CASCI Research

Weighted and Proximity Graphs

The prime example of a Document Network (DN) is the World Wide Web (WWW). But many other types of such networks exist: bibliographic databases containing scientific publications, social networking services, as well as databases of datasets used in scientific endeavors. Each of these databases possesses several distinct relationships among documents and between documents and semantic tags or indices that classify documents appropriately. For instance, documents in the WWW are related via a hyperlink network, while documents in bibliographic databases are related by citation and collaboration networks. Furthermore, documents can be related to semantic tags such as keywords used to describe their content. Given these relations, we can compute distance functions (typically via co-occurrence measures) amongst documents and/or semantic tags, thus creating associative, weighted networks between these items—which denote stronger or weaker co-associations. The figure to the right represents such an associative network of people names extracted from co-occurrence in documents in a database as described in an internal report. You can also see a 3D Video (Real Video) of this network.

Clustering Proximity Graphs
We have used distance and proximity graphs to uncover modules or clusters in the network that may be associated with a particular topic or community of interest. We have applied this clustering methodology to social networks (terrorist networks), keyword networks, scientific journal networks, and citations networks (see our bibliome informatics and adaptive web projects for more details),etc. Recently, we have also used an information-theoretic approach to classify documents of interest in probabilistic graphs of citation co-occurrence in scienticfic citation networks [Kolchinsky et al, 2010].

Semi-metric networks
We study the non-metric network topologies that arise in weighted graphs obtained from real-world data (e.g. co-occurrence statistics). In particular, we have developed measures to extract the graph nodes which most violate the triangle inequality: semi-metric associations. Our working hypothesis is that strong semi-metric associations can be used to identify trends, items with a higher probability of co-occurring in the future, as well the dynamics of such networks in general. This methodology has been successfully applied to networks of published documents, recommender systems for digital libraries at the Los Alamos National Laboratory, web search and recommendation by the givealink.org project, networks of felons obtained from intelligence records, and gene networks (see publications below). This work has been pursued in the Identification of Interests, Trends and Dynamics in Document Networks Project as well as in a Los Alamos Homeland Security LDRD DR project, “Advanced Knowledge Integration (LDRD Reserve)” to discover latent associations in social networks (internal report available). Finally, we are also studying the effects of the various transitive closures that are possible in weighted graphs; namely which closures preserve scale free structure and lead to highest performance in information retrieval. Some of this work has been funded by NSF grant from the Human and Social Dynamics program, With Eliot Smith and Rob Goldstone—this project recently received some attention in the media.

Stochastic model of cut-off behavior
We have developed a stochastic model of vertex aging in networks, to better predict network growth [Simas and Rocha, 2008]. Real world networks display a cut-off in the power-law node degree distributions of complex networks, not expected by the canonical Barabasi-Albert Model. Amaral et al had shown that this cut-off behavior can be computationally modeled with vertex aging. We produced a mathematical model of vertex aging, which allows accurate predictions of the equilibrium point of active vertices and relate network growth with probability of aging.

Funding

Project partially funded by

• Recommendation systems for CareerBuilder.com Project, 2013.
• IARPA Contract: Early Model-Based Event Recognition with Surrogates (EMBERS), 2012-2014.
• National Science Foundation, Human and Social Dynamics Program”, 2005-2008. Project title: “DHB: Dynamics of Information Flow and Decisions in Social Networks”, with Eliot Smith, Robert Goldstone, Hugh Kelly.

Project Members

Selected Project Publications

• T. Simas and L.M. Rocha [2012].”Semi-metric networks for recommender systems“. 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, pp. 175-179.
• T. Simas [2012] “Stochastic Models And Transitivity In Complex Networks”. Ph.D. Dissertation, Cognitive Science, Indiana University.
• A. Kolchinsky, A. Abi-Haidar, J. Kaur, A.A. Hamed and L.M. Rocha [2010]. “Classification of protein-protein interaction full-text documents using text and citation network features.” IEEE/ACM Transactions On Computational Biology And Bioinformatics, 7(3):400-411. DOI: doi.ieeecomputersociety.org/10.1109/TCBB.2010.55
• T. Simas and L.M. Rocha [2008].”Stochastic model for scale-free networks with cutoffs“. Physical Review E, 78(6):066116.
• A. Abi-Haidar, J. Kaur, A. Maguitman, P. Radivojac, A. Retchsteiner, K. Verspoor, Z. Wang, and L.M. Rocha [2008]. Uncovering protein interaction in abstracts and text using a novel linear model and word proximity networks“. Genome Biology. 9(Suppl 2):S11
• The semi-metric methodology has also been used by the givealink.org project. L. Stoilova, T. Holloway, B. Markines, A. Maguitman, F. Menczer [2006]: “GiveALink: Mining a Semantic Network of Bookmarks for Web Search and Recommendation“. Proc. KDD Workshop on Link Discovery: Issues, Approaches and Applications.
• Rocha, L.M., T. Simas, A. Rechtsteiner, M. DiGiacomo, R. Luce [2005]. “MyLibrary@LANL: Proximity and Semi-metric Networks for a Collaborative and Recommender Web Service“. In: Proc. 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI’05), IEEE Press. IEEE Press, pp. 565-571.
• Verspoor, K., J. Cohn, C. Joslyn, S. Mniszewski, A. Rechtsteiner, L.M. Rocha, T. Simas [2005]. “Protein Annotation as Term Categorization in the Gene Ontology using Word Proximity Networks“. BMC Bioinformatics, 6(Suppl 1):S20. doi:10.1186/1471-2105-6-S1-S20
• Rocha, Luis M. [2002]. “Semi-metric Behavior in Document Networks and its Application to Recommendation Systems”. In: Soft Computing Agents: A New Perspective for Dynamic Information Systems. V. Loia (Ed.) International Series Frontiers in Artificial Intelligence and Applications. IOS Press, pp. 137-163.
• Rocha, Luis M. [2002]. “Combination of Evidence in Recommendation Systems Characterized by Distance Functions”. In: Proceedings of the 2002 World Congress on Computational Intelligence: FUZZ-IEEE’02. Honolulu, Hawaii, May 2002. IEEE Press, pp. 203-208. LAUR 02-154.

Back to CASCI Research

The paradigmatic example of a complex system is the web of biochemical interactions that make up life. We still know very little about the organization of life as a dynamical, interacting network of genes, proteins and biochemical reactions. How do biochemical networks—containing many regulatory, signaling, and metabolic processes—achieve reliability and robustness? Cells function reliably despite noisy dynamic environments, which is all the more impressive given that control strategies implemented by intra and inter-cellular processes cannot rely on a centralized, global view of the relevant networks. Are the resulting complex dynamics made up of relatively autonomous modules? If so, what is their functional role and how can they be identified? How robust is the collective computation performed by intra-cellular networks to mutations, delays and stochastic noise? To address these questions, we are focused on developing both novel methodologies and informatics tools to study control and collective computation in automata networks used to model gene regulation and biochemical signaling.

Modeling of biochemical signaling, regulation, modularity, robutsness and emergent computation in the dynamics of complex networks. Our methodology identifies canalizing control patterns in discrete automata models of biochemical networks. Currently working with models of genetic regulation in yeast , flowering of Arabidopsis thaliana; body segmentation in Drosophila, intracellular signal transduction in fibroblasts, biochemical pathways in granular leukemic lymphocytes, an integrated genome-scale transcriptional and metabolic network for E-Coli, and others. Our approach allows us to model biochemical signaling, regulation, modularity [Kolchinsky and Rocha, 2011], robutsness and emergent computation in the dynamics of complex networks modeled as automata networks.

Schema Redescription in Cellular Automata

Schema redescription with two symbols is a method to eliminate redundancy in the transition tables of Boolean automata. One symbol is used to capture redundancy of individual input variables, and another to capture permutability in sets of input variables: fully characterizing the canalization present in Boolean functions. Two-symbol schemata explain aspects of the behavior of automata networks that the characterization of their emergent patterns does not capture. We have used our method to show that despite having very different collective behavior, CA rules can be very similar at the local interaction level [Marques-Pita and Rocha, 2011]—leading us to question the tendency in complexity research to pay much more attention to emergent patterns than to local interactions. We have also used schema redescription to obtain more amenable search spaces of CA rules for the Density Classification Task—obtaining some of the best known rules for this task. [Marques-Pita and Rocha, 2008, Marques-Pita, Mitchell, and Rocha, 2008].

Origin of Representations in Evolving Cellular Automata

We have been interested on the problem of how information, symbols, representations and the like can arise from a purely dynamical system of many components. This is a topic of particular interest in Cognitive Science, where the notions of representation and symbol often divide the field into opposing camps. Often, in the area of Embodied Cognition the idea of self-organization in dynamical systems leads many researchers to reject representational or semiotic elements in their models of cognition. This attitude seems not only excessive, but indeed absurd as it ignores the informational processes so important for biological organisms. Therefore, we have been working both on a re-formulation of the concept of representation for embodied cognition, as well as on simulations of dynamical systems (using Celular Automata) where one can study the origin of representations.

The Evolving Cellular Automata experiments of Crutchfield, Mitchell et al, in the late 1990′s were very exciting, as the ability of evolved cellular automata to solve non-trivial computation tasks seemed to provide clues about the origin of representations and information from dynamical systems [Mitchell, 1998] [Rocha ,1998b]. We conducted additional experiments which extended the density classification task with more difficult logical tasks [Rocha ,2000; Rocha, 2004]. Later, we proposed a re-formulation of the concept of representation in cognitive science and artificial life which is based on this work, but argues that the type of emergent computations observed in these experiments do not produce representations quite as rich as those as observed in biology and cognition [Rocha and Hordijk ,2005]. These experiments allow us to think about how to evolve symbols from artificial matter in computational environments. The figure above, depicts a space-time diagram and particle model of a CA rule evolved to solve the AND task . Some additional Figures and experiment details of CA rules for logical tasks in our experiments are also available.

Project Members and Collaborators

Funding

Project partially funded by .

• Fundacao para a Ciencia e Tecnologia, Portugal. PTDC/EIA-CCO/114108/2009. Project title: “Collective Computation and Control in Complex Biochemical Systems”
• Fundação Luso-Americana para o Desenvolvimento (Portugal) and National Science Foundation (USA), 2012-2014. Project title: “Network Mining For Gene Regulation And Biochemical Signaling.” (171/11)

Selected Project Publications

• M. Marques-Pita and L.M. Rocha [2013]. “Canalization and control in automata networks: body segmentation in Drosophila Melanogaster”. PLoS ONE, 8(3): e55946. doi:10.1371/journal.pone.0055946.
• T. Parmer [2012]. Inducing Apoptosis: The Study of a Random Boolean Network Modelling Survival Signalling in T-LGL Leukemia. Undergraduate Thesis for dual degree, BS in cognitive science and BA in biophysics, through the Individualized Major Program at Indiana University.
• A. Kolchinsky, and L.M. Rocha [2011].”Prediction and Modularity in Dynamical Systems“.In: Advances in Artificial Life, Proceedings of the Eleventh European Conference on the Synthesis and Simulation of Living Systems (ECAL 2011). August 8 – 12, 2011, Paris, France,. MIT Press, pp. 423-430.
• M. Mourao [2011]. Reverse engineering the mechanisms and dynamical behavior of complex biochemical pathways. PhD Dissertation, Indiana University
• A. Kolchinsky, and L.M. Rocha [2011].”Prediction and modularity in complex dynamical systems” (pdf). In: Proc. of the 8th Int. Conf. on Complex Systems. June 26 – July 1, 2011, Quincy, MA, USA. In Press.
• M. Marques-Pita and L.M. Rocha [2011]. “Schema Redescription in Cellular Automata: Revisiting Emergence in Complex Systems“. In: The 2011 IEEE Symposium on Artificial Life, at the IEEE Symposium Series on Computational Intelligence 2011. April 11 – 15, 201, Paris, France,. IEEE Press, pp: 233-240.
• M. Marques-Pita, M. Mitchell, and L.M. Rocha [2008]. “The Role of Conceptual Structure in Learning Cellular Automata to Perform Collective Computation“. In: Unconventional Computation: 7th International Conference (UC 2008). Lecture Notes in Computer Science. Springer-Verlag, 5204: 146-163.

• M. Marques-Pita and L.M. Rocha [2008]. “Conceptual Structure in Cellular Automata: The Density Classification Task“. In: Artificial Life XI: Eleventh International Conference on the Simulation and Synthesis of Living Systems. S. Bullock, J. Noble, R. A. Watson, and M. A. Bedau (Eds.). MIT Press, pp. 390-397.
• Rocha, Luis M. and W. Hordijk [2005]. “Material Representations: From the Genetic Code to the Evolution of Cellular Automata”. Artificial Life. 11 (1-2), pp. 189 – 214
• Almeida e Costa, F. and Rocha, Luis M. [2005]. “Embodied and Situated Cognition”. Artificial Life. 11 (1-2), pp. 5 – 11
• Rocha, Luis M. [2004]. “Evolving Memory: Logical Tasks for Cellular Automata”. Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9). Boston, Massachusetts, September 12-15th 2004.
• Rocha, Luis M. [2001]." Evolution with Material Symbol Systems." Biosystems. Vol. 60, pp. 95-121.

• Rocha, Luis M. [2000]. “Syntactic autonomy, cellular automata, and RNA editing: or why self-organization needs symbols to evolve and how it might evolve them”. In: Closure: Emergent Organizations and Their Dynamics. Chandler J.L.R. and G, Van de Vijver (Eds.) Annals of the New York Academy of Sciences. Vol. 901, pp 207-223.

Complex Networks Collaboratory

Cx-Nets  is a virtual collaboratory of three research groups that despite their far apart geographical locations pursue the same research agenda in close collaboration. Active research areas include:

• Network theory, structure and models
• Information Networks
• Epidemic modeling
• Social systems
• Infrastructures
• Biological networks

The Cx-Nets website is also intended as an information exchange point with links to conferences, tools and references useful for the network science community.

Research | People | Academics | News and Meetings | Publications-online | Media Mentions | Relevant Conferences

Complex Adaptive Systems and Computational Intelligence

We are a research group at Indiana University and the Instituto Gulbenkian de Ciencia working on complex systems. We are particularly interested in the informational properties of natural and artificial systems which enable them to adapt and evolve. This means both understanding how information is fundamental for the evolutionary capabilities of natural systems, as well as abstracting principles from natural systems to produce adaptive information technology.

Our research projects (see below) are on computational and systems biology, complex networks, text and literature mining, evolutionary systems, adaptive search and recommendation, cognitive science, artificial life, and biosemiotics. Additional information available on Luis Rocha’s Website and our group page at the Instituto Gulbenkian de Ciencia.

For information on joining our group see our Academics page. As a group, we are seriously interconnected with other research groups and networks: The Center for Complex Networks and Systems (CNets), Alife@IU, Biocomplexity Institute, Cognitive Science Program, Complex Systems & Networks, FLAD Computational Biology Collaboratorium, InfoVis Lab, Instituto Gulbenkian de Ciencia, Networks an Agents (NAN).

You are welcome to join our mailing list CASCI-L by either:

• sending an e-mail to listserv@indiana.edu with subscribe CASCI-L in the body (with no subject), or
• via the LISTSERV web interface: https://listserv.indiana.edu/cgi-bin/wa-iub.exe?HOME ; Click Subscriber’s Corner at the top of the page. Search for “CASCI-L” select it and click Submit.

CASCI projects

CNetS Professor Alex Vespignani has been elected to fellowship in the American Physical Society, the preeminent organization of physicists in the United States. Vespignani was honored for his contribution to the statistical physics of complex networks, in particular his seminal work on the spreading of viruses in real networks. More…

No, it’s not an Italian spin-off of the popular TV show. CSI Piemonte is organizing a meeting on Understanding Complexity: a Journey through Science to be held November 22-23 at the Lingotto Convention Center here in Torino. We will have demos and posters on 6S, GiveALink, and the egalitarian effect of search engines. I look forward in particular to seeing my good old friend Dario and my mentor, Domenico.