Keynote Speakers

The architecture of complexity: From the topology of the WWW to the structure of the cell

Abstract

Systems as diverse as the world wide web, Internet or the cell are described by highly interconnected networks with amazingly complex topology. Recent studies indicate that these networks are the result of self-organizing processes governed by simple but generic laws, resulting in architectural features that make them much more similar to each other than one would have expected by chance. I will discuss the amazing order characterizing our interconnected world and its implications to network robustness, social networks and potentially human diseases.

Synchronization and intervention of locally interacting multi-agent systems

Abstract

Multi-agent systems (MAS) arise from diverse fields in natural and artificial systems, e.g., schools of fish, flocking of birds, swarm intelligence and the coordination of autonomous mobile robots, etc. Generally speaking, MAS are composed of many agents which interact with each other by either local or global rules, or both. Even with only local interactions, the whole system may still emerge some kinds of collective behaviors, such as, consensus, synchronization, clustering, whirlpool, etc., which are macroscopic properties of the MAS. The understanding of the emergence phenomena from local to global (or from micro to macro), is a basic problem in the study of complex systems.

In this paper, we will work with a basic class of MAS, where each agent has the tendency to behave as other agents do in its neighborhood. This is a typical phenomenon in many MAS, especially in biological systems, and such a property is well captured by the so called Vicsek model. This model possesses some key features of the MAS, such as dynamic behavior, local interactions, and changing neighbor graphs. The simulations done by Vicsek and his coauthors tell us that all agents will eventually move in the same direction (synchronization) when the density is large and the noise is small. This model looks simple, but the nonlinear coupling relationship between the positions and headings makes the theoretical analysis quite involved. In fact, almost all of the existing studies have to resort to a certain kind of connectivity assumptions, which are difficult and troublesome issues in themselves.

In the first part of this talk, we will present some recent progress in the synchronization analysis of the above mentioned Vicsek model. We will give a complete theoretical analysis of this model without imposing any connectivity conditions. The main technical results are the following: a) For any given and fixed model parameters concerning with both the interaction radius r and the agents' moving velocity v, the overall system will synchronize as long as the population size n is large enough, which is consistent with the simulations given by Vicsek et al; b) If both r and v decrease as the population size n increases, but satisfy a certain decaying rates, then again, the overall system will synchronize for large n.

In the second part, we will address the problem of intervention of MAS. In many real applications, it is difficult or impossible to change the local rules of the agents, such as, the human customized behavior, the moving strategies of animals. Then what is the feasible way to intervene such kinds of MAS? To answer this question, we will propose a new notion called "soft control", which is different from the traditional approach of distributed control. To demonstrate the feasibility, we will consider two ways to intervene such MAS in this talk. The first one is to use a small portion of "information" agents, and the second one is to design one or more "intelligent" agent(s). In the first case, we will show that the proportion of the information agents needed will tends to zero as the population size increases to infinity. In the second case, we will give some examples to show how to design one or a few "intelligent" agents.

Finally, we will present some interesting problems for future investigation.

Characterizing node activity and local effect in complex networks

Abstract

Node activity, local effect, asymmetric topology and preferential attachment are basic characteristics of realistic networks focused in network science. Each active node is an independent acting agent, having different energy and uncertainty. Local effect of nodes is the result of node activity interaction, that is, each node affects its neighboring nodes, and at the same time, its neighboring nodes also affect itself. Moreover, this effectiveness will gradually decrease with the increase of distance, without any centralized control upon it. Furthermore, complex networks have other typical properties, such as asymmetric topology which presents as clustering nodes, and preferential attachment in network growing which is different from random attachment.

The nonlinear interactions between different parts of complex networks cause the emergent properties of whole network. As we know now, the emergent mechanism from the simple local interactions to the global collective behaviors is the core issue of network science research. The known common measures, such as degree distribution, betweenness distribution, clustering coefficient and average path length, etc., are used to characterize general statistical regulations. However, all the above measures are hard to characterize the inherent rules behind the emergent properties. For example, degree may be used to measure the connection ability of a node, while betweenness characterizing the ability of flow bridging, and clustering coefficient characterizing the phenomena of structural clustering, etc. Different measurement ways may get different results, and it is difficult to mix and measure the node ability of interaction, connection and localization.

From the classic concept of field introduced by M. Faraday in 1837, the field as an interpretation of non-contact interaction between particles in every different granularity, from atom to universe, had attained huge success. In a potential field, potential means the work done to move a unit object, such as a mass point or a charge point, from some position to the reference point. Data field introduced in 1999 by our group, as the main method in cognitive physics, reflects field model into the data space. It is a virtual field, describing the relationship among data point in coordinates, could be used to dig out data characteristics.

The locality of a node in network reflects its position potential, named as topological potential, which characterizes its ability of affecting other nodes, and the result of other nodes interaction effect overlapping. Topological potential and its distribution focus on the structural localization conduced by node activity. Considering a node in network as a potential source, it can affect others along with paths connecting each other. Hence all of nodes in a network affect each other by their potential fields overlapping. The potential field in networks does not like other classic field owning Euclidean distance, so we replace Euclidean distance by jumps between two nodes.

We will further discuss the choice of potential functions and the optimal effect factor, which is used to characterize the mathematical law of nodes interaction. In order to uncover the physical measures behind nodes potential interactions, we compared the common measure ways, such as degree, betweenness, closeness centrality and each of their distribution. It should be especially pointed out that topological potential along with paths between nodes cannot be measured simply by those common measure ways. Topological potential emphasizes nodes connection pattern, local activity, which leads to the emergent patterns of different connections, and is also helpful to understand the dynamics of networks.

In real world, each node has many reality attributes, reflecting different node activity. Topological potential regards these attributes as a source of the node ability, named as mass of node, affecting other nodes. The emergence and evolution of complex networks are the interaction result of nodes localizing with different reality attributes.

As an illustration and application of topological potential, we have carefully analyzed nodes ranking, community detecting, bridging nodes detecting, kernel membership of community discovering and so on, took Krebs' political books online-selling network as the main demonstration. In the demonstration network, nodes represent real time best seller (books) about US politics sold by the online bookseller Amazon, and edges represent frequent co-purchasing of books by the same buyers, as indicated by the "customers who bought this book also bought these other books" feature on Amazon. We conclude that the partial order ranking, as the form of top N is useful to some actual problems, comparing the ranking result with other well-known algorithms, such as PageRank and HITS. We also conclude that nodes cluster by topological potential effect, forming different communities. Some nodes are kernel to a community for they localize in the topology attracting kernel. Some other nodes bridge among different communities for they are affected equally by these communities.

Spreading processes in complex techno-social networks

Abstract

In different contexts we are challenged by multi-scale networks where infrastructures composed by different technological layers are interoperating with the social component that drives their use and development. Examples are provided by the Internet, the social Web, the new WiFi communication technologies and transportation and mobility infrastructures. The multi-scale nature and complexity of these techno-social networks are crucial features in the understanding of these systems and the dynamical processes occurring on top of them.

We will discuss the central statistical features of these networks and their impact on epidemic, contagion and spreading processes in both the biological world and the ITC domain. We will present the development of realistic computational models based on the network paradigm and the reaction-diffusion processes framework that allows their theoretical understanding. Finally we will analyze the central role of complex networks thinking in the definition of predictive large scale computational approaches for the modeling of emergent disease spreading.