Add a submissionDelete submission(s)Deleted submissionsUpdate a submissionEmail to authorsHide abstractsDownload submissions

NETSCI 09 list of submissions

Shortcuts to papers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188

1: Gal Oestreicher-Singer and Arun Sundararajan. The Visible Hand of Social Networks in Electronic Markets    submission   information
Abstract. The sustained increase in different forms of electronic interaction over the last decade has led to the emergence of a number of electronic and visible networks that connect consumers, products and businesses. In this paper, we conjecture that the visibility of these networks influences a wide variety of choices and outcomes in electronic markets, and analyze the nature and extent of influence that their visibility induces. We do so by developing an extended model of social or “peer” effects that separates network-induced social influence from demand correlations that are caused by product complementarity, by product characteristics, and by self-selected groupings. Our main analytical result provides a simple set of conditions under which the influence that visible social networks have on demand can be econometrically identified, and we show that our conditions place very minimal empirical restrictions on the structure of the networks that define the pattern of social influence. We estimate this model using data about the demand and co-purchase networks for over 250,000 books offered on over the period of a year. Our empirical results show that the explicit visibility of a copurchase
relationship more than triples the average influence that complementary products have on each others’ demand. Furthermore, the magnitude of this social influence is higher for more popular books, for more recently published books, and varies in counter-intuitive ways with changes in pricing, secondary market activity and assortative mixing across product categories. Our paper presents new evidence quantifying the role of network “position” and the influence of visible social networks in electronic markets, highlighting the power of basing virtual shelf position or slotting on consumer preferences that are revealed through shared purchasing patterns. It also offers new results for the identification of peer effects which reverse the impossibility issue associated with the reflection problem of Manski (1993), establishing in the process that robust identification is simplified considerably when there are multiple overlapping networks mediating peer influence.
2: Mason Porter. Community Structure in Online Collegiate Social Networks    (abstract only)   information
Abstract. We apply the tools of network analysis to study the roles of university organizations and affiliations in structuring the social networks of students by examining the graphs of Facebook “friendships” at 100 American universities at a single point in time.  We investigate each single-institution network’s community structure and examine the correlations between the network communities and a set of self-identified user characteristics. We also study single-gender subsets of the university networks and investigate the impact of incomplete demographic information in the data. Our study across many universities allows us to make comparative observations about the online social lives at the different institutions, which can in turn be used to infer differences in offline lives.  From a more general standpoint, our study illustrates how to examine different instances of social networks constructed in similar environments.
3: Mario Chavez, Miguel Valencia, Vito Latora and Jacques Martinerie. Functional modularity of spontaneous activities in normal and epileptic brain networks    (abstract only)   information
Abstract. There is a growing interest in studying the connectivity patterns extracted from brain signals during different mental states. Current studies suggest that brain architecture leads neural assemblies to be coordinated with an optimized wiring cost. Brain webs would be organized as a mosaic of brain modules, carrying out specific functional tasks and integrated into a coherent process. This modular structure -natural divisions of network vertices into densely connected subgroups- would be similar to that observed among real-world networks from related proteins to social groups. In this work, we show our results for the characterization of the modular structure of brain networks extracted from brain signals in epileptic patients and healthy subjects. Using a random walk-based method we are able to identify a non-random modular architecture of brain connectivity. This approach is fully data driven and relies on no a priori choice of a seed brain region or signal averaging in predefined brain areas. Interestingly, the spatial distribution of the retrieved modules matches with brain areas associated with specific functions, assessing a functional significance to the modules. By means of this approach we find that in healthy brains the nodes of the network are mainly connected to other nodes in the same module, whereas the brain connectivity of epileptic patients exhibits a modular organization where nodes are interconnected with different modules of the network. Results suggest that this modular configuration might play a key role in the integration of large scale brain activities, facilitating the emergence of epileptic discharges.
4: Hasan Guclu and Murat Yuksel. Dynamic Limited Scale-Free Models for Unstructured Peer-to-Peer Networks    (abstract only)   information
Abstract. Several protocol efficiency metrics (e.g., scalability, search success rate, routing reachability and stability) depend on the capability of preserving structure even over the churn caused by the ad-hoc nodes joining or leaving the network. Preserving the structure becomes more prohibitive due to the distributed and potentially uncooperative nature of such networks, as in the peer-to-peer (P2P) networks. Thus, most practical solutions involve unstructured approaches while attempting to maintain the structure at various levels of protocol stack. The primary focus of this paper is to investigate construction and maintenance of scale-free topologies in a distributed manner without requiring global topology information at the time when nodes join or leave. We consider the uncooperative behavior of peers by limiting the number of neighbors to a pre-defined hard cutoff value (i.e., no peer is a major hub), and the ad-hoc behavior of peers by rewiring the neighbors of nodes leaving the network. We also investigate the effect of these hard cutoffs and rewiring of ad-hoc nodes on the P2P search efficiency.
5: Andrea Mario Lavezzi and Nicola Meccheri. Transitions Out of Unemployment: the Role of Social Networks' Topology and Firms' Recruitment Strategies    submission   information
Abstract. In this paper we adopt the probabilistic framework of Calvò-Armengol and Jackson (2004) to study the effects of job contact networks on out-of-unemployment transitions. In particular we evaluate the role of different network topologies vis-a-vis state-dependent probabilities of receiving information on vacancies, which we relate to different firms' recruitment strategies. We find that social connections produce sizable increases in upward mobility from unemployment and, in general, symmetric network topologies perform better than asymmetric ones. In addition, and most interestingly, these results strongly depends on the different hypotheses on the firms' hiring process strategy. Furthermore, in scale-free networks the probability of transitions out of unemployment increases in the exponent of the power-law degree distribution, but its value is much lower than what obtainable in Poisson random networks.
6: Sung-Guk Han, Su-Chan Park and Beom Jun Kim. Reentrant phase transition in a predator-prey model    (abstract only)   information
Abstract. Submission for a contributed talk.


We numerically investigate the six-species predator-prey game in complex
networks as well as in $d$-dimensional hypercubic lattices with $d=1,2,\cdots, 6$.
The interaction
topology of the six species contains two loops, each of which is composed of
cyclically predating three species. As the mutation rate $P$ is lowered below
the well-defined phase transition point, the $Z_2$ symmetry related with the
interchange of the two loops is spontaneously broken, and it has been known
that the system develops the defensive alliance in which three cyclically
predating species defend each other against the invasion of other species. In
the `small-world network structure characterized by the rewiring probability
$\alpha$, the phase diagram shows the reentrant behavior as $\alpha$ is varied,
indicating a twofold role of the shortcuts. In $d$-dimensional regular
hypercubic lattices, the system also exhibits the reentrant phase transition as
$d$ is increased. We identify universality class of the phase transition
and discuss the proper mean-field limit of the system.
7: Stephen Uzzo. Network Visualization: Striving for Understanding    (abstract only)   information
Abstract. While network visualization is vital to increasing the understanding of network structures and dynamics among researchers, for the general populace, network graphs signify little more than an archetype for the idea of networks. As the reach of network science extends into more aspects of, not only research, but also the day-to-day parlance of lay people and policymakers, data understandability takes on an increasingly important role.

As we develop more sophisticated approaches to network visualization to keep pace with discoveries in network science, we also need to consider this expanding audience for our work, and the need to educate the next generation of network scientists in the use of the tools and interpretation methods for network visualization.

This points to a need for increased graphical literacy and the kinds of tools available to allow everyone to, not only use such tools for understanding complex processes in nature as they are described by the interpreters (scientists); but also be competent to make discoveries in data sets and model outcomes with some degree of accuracy using such tools: for them to be predictive rather than just prescriptive. This paper will discuss the significance of this trend, salient research and how it is being applied to science communications in informal learning environments.
8: Brian Karrer and M.E.J. Newman. Random acyclic graphs    (abstract only)   information
Abstract. Submission is for a contributed talk.  If there is not room in the schedule for it, please consider it as a poster.


Directed acyclic graphs are a fundamental class of networks that includes citation networks, food webs, and family trees, among others.  We define a random graph model for directed acyclic graphs and give solutions for a number of the model’s properties, including connection probabilities, as well as a fast algorithm for simulating the model on a computer.
9: Katherine Krumme. Social and Economic Dynamics in an Online Peer-to-Peer Lending Network    (abstract only)   information
Abstract. Introduction

Economic transactions have long taken place over social networks; in recent years, an increasing number of models have facilitated borrowing within groups rather than from centralized lenders. Microfinance has proven viable where small-group ties enforce reputation and default rates are minimized [1]. Is has not yet been determined whether reputation and social ties sufficiently strong in an online network of strangers to make peer-to-peer lending a viable model, both from the perspective of borrower access (risk assessment by lenders) and that of loan repayment (expected utility of lenders).

In this paper I (with collaborators) characterize the network of a peer-to-peer lending marketplace, in which edges describe a specific economic relationship between two agents, rather than a connection that can be created without (or with low) cost, risk, or reward (as is the case for link-creation in many online social networks). We consider 350,000 loan listings, bid histories, and accompanying member profiles from the online lending network [2].  In addition, we study the co-occurring social network (of online “friendship” and affinity groups), where links are costless but signal a measure of reputation over the economic network. Understanding the static and dynamic characteristics of a peer-to-peer network can yield insights about human behavior, as well as serve to improve the model for lenders and borrowers.


Herding behavior

Social influence can manifest itself between members who have no direct link, either through a lending partnership or by shared group membership. A lender’s decision to bid on a listing, for example, may be based on the implicit support of the borrower by other marketplace members. To test this hypothesis, we examined the rate at which bids were accrued to listings (The Prosper marketplace is such that lenders bid incrementally on a listing; if a listing fails to garner complete funding, it is canceled by the system).

From the bid history of completed loans, we found that percentage funding asymptotically approaches the maximum, but that initial funding occurs slowly and then accelerates once an initial number of “pioneer” bids are placed. A large number of bids (9.75% of total) also occurs on a small percentage of fully-funded loans as lenders bid down the interest rates of the best loans.

Evidence of learning

A large portion (91%) of listings never garner sufficient bids to convert to loans. We examine the behavior of would-be borrowers who repost a listing after it expires unfulfilled, and find that, of the minority that reposts rather than exiting the network, 70% re-list only once, and that fewer than 2% of borrowers exhibit learning in the form of altering the amount requested.

Although further textual analysis of listing descriptions is needed, we see the above results as preliminary evidence that borrowers are either not learning -- that is, are not adjusting their interest rates and requested amounts to levels appropriate given their financial history, or that there is something endemic in the marketplace (a poor search function, for example) that prevents some borrowers from being matched to the lenders who would prefer their given profile.

Network characteristics

While a small number of borrowers in the peer-to-peer marketplace go on to support the network by acting as lenders, we find an extremely low clustering coefficient in the network of economic links. A visualization of a subgraph –using Network Workbench [4]-- finds that most components exhibit a tree-like structure. However, the network of friendships and shared affinities shows power-like degree distributions and greater clustering, on the order of that observed in other online social networks.

We find, in addition, that participation in the social network, especially as a member of a group with a high reputation (as determined by Prosper on a scale of 1 to 5), increases the probability of both loan conversion (by almost three times, 17.7% probability versus 6.1% for no group) and of loan repayment (by 1.9% percent late versus 31.1% late for no group). Other analysis [3] has found similar effects for participation in the social network.

Lenders make sub-optimal decisions

One of the aims of online peer-to-peer lending is to allow the “underbanked” and those with low credit ratings to build a reputation that can extend from this marketplace to others. However, our analysis finds that lenders maximize their expected by payoff by lending only to those borrowers in the highest credit brackets: that is, credit score is one of the best features for predicting loan repayment (as determined by greedy and forward-backward feature selection methods), and interest rates in the lowest credit brackets are not sufficiently high to make the risk-opportunity tradeoff maximal. The only element that serves the underbanked, currently, is the imperfect diffusion of information to lenders.


Our results suggest that the peer-to-peer marketplace serves neither borrowers nor lenders optimally; in addition, the marketplace itself suffers when loan volume is slack, as revenues are proportional to completed transactions.

Decision-making in peer-to-peer networks differs from that in lending models at banks; in the former model, lenders have access to subjective factors (e.g. loan description) as well as the judgment of others (through observation of bid dynamics). However, we find that lenders make these decisions poorly, that there exists little learning by borrowers, and that the network exhibits low economic clustering despite modest clustering in the social network. These results point to existing shortcomings in the online lending model, as well as to a number of structural changes that could enable more optimal transaction patterns.


[1] Grameen Bank.
[2] Prosper Marketplace.
[3] J.Ryan, K.Reuk, C.Wang, “To Fund Or Not To Fund: Determinants Of Loan Fundability in the  Marketplace.”, Stanford Graduate School of Business.
[4] NWB Team. (2006). Network Workbench Tool. Indiana University, Northeastern University, and University of Michigan,
[5] M. E. J. Newman. The structure and function of complex networks. SIAM Review,
45(2):167–256, 2003.
[6] S. Knack, P. Keefer. Does Social Capital Have An Economic Payoff? A Cross-Country Investigation, Quarterly Journal of Economics, 1997.
10: Karsten Steinhaeuser, Nitesh Chawla and Auroop Ganguly. Discovery of Climate Patterns with Complex Networks    (abstract only)   information
Abstract. Climate scientists have applied various clustering methods to discover patterns in historical data, for example regions that share some common climatological behavior. However, such approaches are limited in that they (i) often only consider a single variable (ii) view time series data as multi-dimensional feature vector (iii) lack the ability to capture long-range relationships. We address these issues by employing a complex network (graph) representation of the data. Nodes correspond to physical locations around the globe, and edges are placed between them based solely on their climatologic similarities; to incorporate the temporal nature of the data, a multivariate cross correlation function is used to weight the network edges. This weighted network approach offers a more powerful and versatile representation of the data.

We start with 60 years of historical data for temperature, precipitable water, pressure, and relative humidity, divide it into 5-year windows, and construct a separate network from each period to study the network dynamics over time. We then apply a community detection algorithm to each network to identify climate regions and show that these "communities" have a climatological interpretation; for example, we are able to find teleconnections between South America, Africa, and India that are likely linked to the El Nino Southern Oscillation. Tracking communities over consecutive periods allows us to study structural changes, and disturbances in structure can be an indicator of climate events. Finally, we discuss how this model can be extended for the discovery of more complex concepts such as dependence structure between climate extremes or discovery of multivariate climate indices.
11: Sumeet Agarwal, Nick Jones, Charlotte Deane and Mason Porter. Node and link roles in protein interaction networks    (abstract only)   information
Abstract. A key question in modern biology is how the complexity of protein interaction networks relates to biological functionality. One way of understanding the set of proteins and their interactions (the interactome) is to look at them as a network of nodes connected by links. By studying the structure of this network, we may hope to learn something about the interactome's organisation. Here we attempt to look at different approaches for using network models to assign structural and functional roles to proteins and protein interactions. It has been proposed that highly connected nodes, or hubs, in the interactome fall into two classes, 'date' and 'party', and that these play a key role in the modular organisation of the yeast interactome. This classification was made on the basis of the extent to which hubs are co-expressed with their interaction partners, but was then used to impute to them specific topological roles. We attempt to use purely topological measures to examine the extent to which these hubs really fall into the roles thus attributed. We use a community detection approach based on maximising modularity to partition the interaction network into functionally coherent modules. We then assign roles to proteins based on how their interactions are distributed within their own module and across other modules. Based on a study of multiple yeast and human datasets, our results suggest that there is little evidence for a clear date/party distinction, but rather nodes in the protein interaction network seem to perform a variety of roles falling along a continuum, and there is no strong correlation between these roles and co-expression. We also examine alternative approaches to studying topological roles. So far, most work has focused on node-centric measures; here we attempt using a betweenness metric to quantify the centrality of links rather than nodes. We show that this measure relates to protein functional similarity as assessed by annotation overlap in the Gene Ontology, and may also be relevant to understanding how the interactome works as a system.

(For Poster)
12: Samuel Arbesman and Nicholas Christakis. Leadership Insularity: connectivity and insularity between central nodes in networks    (abstract only)   information
Abstract. In recent years, there has been a wide variety of research into two areas of network measurement: community identification and node centrality. Here we attempt to combine these methods to create a novel metric known as leadership insularity. By determining the most highly connected nodes within each community of a network, we are able to determine the 'community leaders' within the graph. And in doing this, we have the basis for a novel metric that examines how connected, or disconnected, the leaders are to each other. This measure of insulation, known here as leadership insularity, has a number of appealing measurement properties and provides a new way of understanding how network structure can affect its dynamics, especially information flow. We explore the leadership insularities of a large variety of networks and how it relates to the diverse functions of these networks.

This is for a contributed talk.
13: Mônica G. Campiteli, Frederico Soriani and Gustavo H. Goldman. Poster - The role of the gene ATM (Ataxia Telangiectasia Mutated) in the co-expression network of the model organism Aspergillus nidulans.    (abstract only)   information
Abstract. The human syndrome Ataxia telangiectasia (AT) is an inherited neurological disorder that affects individuals mutated in the atm gene. The disease is characterized mainly by a progressive cerebellar degeneration, hypersensitivity to ionising radiation and genomic instability. Some aspects of the phenotype remains unclear and recent studies suggest a role of mitochondria in the neuron's fate. The fungus Aspergillus nidulans can be studied as a model organism to the unravelling of the AT phenotype and some features of the mutated atm homolog (deltaAtmA) have been related to the AT human neurons such as a defect in the maintenance of a stable axis of polarization.
In this work we have constructed the co-expression networks from microarray data of A. nidulans deltaAtmA and wild type strains. The analysis and comparison of the obtained networks revealed some aspects of the disease that implicate some hypoxia-related genes in the fungus mutated phenotype.
To achieve the results we have developed a methodology for the inference of co-expressivity from very short microarray series. The method was able to infer dependency between series composed of as few as three time points and showed robustness and a high relevance when confronted with biological evidence.
The present work represents a significant contribution to the understanding of the AT syndrome and gives its contribution to the exploration of microarray data and biological networks.
14: Cesar A. Hidalgo and Ricardo Hausmann. Economic Complexity and Economic Development    (abstract only)   information
Abstract. For Adam Smith, wealth was related to the division of labor. As people and firms specialize in different activities, economic efficiency increases, suggesting that development is associated with an increase in the number of individual activities and with the complexity that emerges from the interactions between them. Here we develop a view of economic growth and development that gives a central role to the complexity of a country’s economy by interpreting trade data as a bipartite network in which countries are connected to the products they export, and show that it is possible to quantify the complexity of a country’s economy by characterizing the structure of this network. Furthermore, we show that the measures of complexity we derive are correlated with a country’s level of income, and that deviations from this relationship are predictive of future growth. This suggests that countries tend to converge to the level of income dictated by the complexity of their productive structures, indicating that development efforts should focus on generating the conditions that would allow complexity to emerge in order to generate sustained growth and prosperity.
15: Massimo Ostilli and Jose' Fernando Mendes. Communication and correlation among communities    submission   information
Abstract. {TALK}
Given a network and a partition in n communities,
we consider the issues ``how communities influence each other''
and ``when two given communities do communicate''.
Specifically, we address these questions in the context of small-world networks,
where an arbitrary quenched graph is given and long range connections are randomly added. It's possible to prove that, among the communities,
a simple superposition principle applies and gives rise to a natural generalization
of the effective field theory already presented in [Phys. Rev. E 78, 031102] (n=1), which here (n>1) consists in a sort of effective TAP (Thouless, Anderson and Palmer) equations in which each community plays the role of a microscopic spin.
The relative susceptibilities derived from these equations calculated at finite or zero temperature, where the method provides an effective percolation theory, give us
the answers to the above issues.
Unlike the case n=1, due to the tap-like structure of the equations, asymmetries among the communities may lead to many metastable states whose number,
in the case of negative short-cuts among the communities,
may grow exponentially fast with n.

As immediate examples we consider the n Viana-Bray communities model
and the n one-dimensional small-world communities model.
Despite being the simplest ones, the relevance of these models in
network theory, as e.g. in social networks, is crucial and no
analytic solution were known until now.
Finally, we show how, from the relative susceptibilities,
a natural and efficient method to detect the community structure of a generic network arises.
16: Francesco Rao. Protein dynamics: complex network analysis of energy landscapes    (abstract only)   information
Abstract. Proteins are essential macromolecules for life and are responsible for most cellular functions. It is now a consolidated result that protein function depends critically on the synergy of structure and dynamics, i.e. the spatial arrangement of protein atoms and the time evolution of the latter in different spatial configurations (or conformational states). However, the molecular mechanism which connects protein function with structure and dynamics is not fully understood.

      Investigation of protein dynamics is a very difficult task to achieve experimentally, even for high resolution approaches like single-molecule FRET, X-ray crystallography or NMR. Numerical simulations has given a new perspective on protein motions providing a link between structure and dynamics. In the past years many improvements, both computational and theoretical, have been done to increase computers speed, accuracy of the models and reliability of the simulations.

      Energy landscape theory is a useful framework for describing and understanding protein dynamics. The fascinating idea behind this approach is that the stable states of the system are the local minima of the potential energy multidimensional surface and the height of the saddles between them determines the rates of the transitions. At finite temperature, when the entropic contributions are relevant, the dynamics of the system is governed by the free energy instead of the potential energy only. The intrinsic complexity and multidimensionality make the landscape an untreatable object. For this reason, the free-energy landscape is usually projected onto one or two arbitrarily chosen order parameters making its usefulness pretty limited.

     Here, we present an approach to describe the free-energy landscape of a protein system in much more detailed way. Based on complex networks, this method has been successfully applied for the analysis of protein folding and isomerization by MD simulations as well as electron transfer and time-resolved IR spectroscopy experiments.
17: Adam Hackett, Sergey Melnik and James Gleeson. The role of high degree nodes in global cascades on random networks: an analytical approach    (abstract only)   information
Abstract. Poster

In their paper ``Seed size strongly affects cascades on random networks'' (Phys.Rev. E, 75, 056103 (2007)) Gleeson and Cahalane determined, analytically, the average cascade size in the Watts model of threshold dynamics on random networks of arbitrary degree distribution. Existence criteria for global cascades were shown to depend sensitively on the size of the initial seed disturbance. We have extended these results to include the effect of influentials (high degree nodes); as defined by Watts and Dodds in ``Influentials, Networks, and Public Opinion Formation'' (Journal of Consumer Research 34 Dec. 2007). The new analytical expressions derived allow us to compare the cascade dynamics instigated by influentials with those instigated by average members of the population. Connections between these results and the zero-temperature random-field Ising model on random graphs are also discussed.
18: Ernesto Estrada and Naomichi Hatano. From Networks to Hypernetworks    (abstract only)   information
Abstract. We introduce the concept of communicability in complex networks and find its spectral formula. We show that it corresponds to the thermal Green's function of the network. Using such function we develop the concept of communicability graph which permits to find all the communities and their overlapping in the network. Such overlapped communities form a hypergraph or hypernetwork. We develop an algorithm for finding such hypernetworks for different levels of overlapping between the communities. Then, we introduce the concept of temparature for complex networks in this context. Using the thermal Green's function for different values of temperature we study the evolution of the hypernetworks and we observe some general properties characteristics of the topological structures of such hypergraphs.
19: Carlos Lever. A model of political campaigns, advertising and lobbying over networks    submission   information
Abstract. Abstract submitted for talk.

We present a game-theoretic model where two political parties strategically compete by spending to persuade voters who are in turn influenced by the opinion of their neighbors on a social network. Our main finding is that in equilibrium parties spend on each voter in proportion to their DeGroot measure of network influence. These weights do not depend on the initial opinion of each voter. Without the network each party spends in proportion to the probability each voter has of being pivotal. We can extend our results to two firms competing to market their product, where we find that each firm spends in proportion to the Bonacich measure of network centrality. In all cases players spend less on voters with more extreme opinions; and if party A increases it's resources relative to party B, then both parties increase the percentage they spend on to voters who were more likely to vote for B. Our results hold for elections that require a qualified majority, so our model can also be applied to lobbying in congressional commissions.
20: Elka Korutcheva and Kostadin Koroutchev. Statistical Mechanics of Texts: Message Passing Approach    (abstract only)   information
Abstract. In this article we present a model of human written text, based on statistical mechanics approach.
By using large text corpus we derive the energy for the different words from their frequency distribution.
We show that the thermodynamic parameters have a strong correspondence with important quantities from the statistical linguistics.
The "specific heat" parameter shows to separate effectively the different semantic classes of words used in the text as specific terms, common words and function words.
Defining hierarchical hyper-graph on the text, connecting only the equal words and the consecutive words that are strongly grammatically interrelated, we can build a more precise statistical physics model of the text by using message passing algorithms.
It results that this representation extracts well the semantic structure of the texts.
21: Juan Pablo Cárdenas, Mary Luz Mouronte, Luis Moyano, Maria Luisa Vargas and Rosa M. Benito. Complexity and Robustness in the Spanish Optical Telecommunication Network    (abstract only)   information
Abstract. In this communication we present a study of the topology and robustness of the SDH telecommunication network operated by Telefónica in Spain. SDH (Synchronous Digital Hierarchy) networks transport different traffic types, such as voice, video, multimedia, and data packets (as those generated by IP) over the same fiber wire. Our results showed emergent complexity in all the Spanish provincial networks analyzed, despite being largely dependent on strict planning policies [1,2]. Particularly, we found power-law scaling in the degree distribution and properties of small-world networks, signs of self-organization in the evolution of complex systems. These complex topological properties have been related to the robustness of systems. Thus, complex networks are considered robust against random failures but sensitive to planned attacks in highly connected nodes. Under this perspective, in this work we also present a study of the robustness of the Spanish SDH network by the simulation of direct attacks to those equipments that control the flow of information. We have found that the robustness depends not only on the connectivity of equipments but also on the capacity and type of links associated to those equipments. Consequently we have also observed that the robustness of SDH networks depends on the particular initial design and evolution of each Spanish province.

[1] J. P. Cárdenas, M. L. Mouronte, A. Santiago, V. Feliu and R. M. Benito “Complex topology in optical transport networks”, International Journal of Bifurcation and Chaos. Submitted.

[2] A. Santiago, J. P. Cárdenas, M. L. Mouronte, V. Feliu and R. M. Benito, “Modeling the topology of SDH Networks”. International Journal of Modern Physics C 19 (2008) 1809-1820.
22: Mary Luz Mouronte, Juan Pablo Cárdenas, Antonio Santiago, Victor Feliu and Rosa M. Benito. Modelling Spanish Optical Transport Networks    (abstract only)   information
Abstract. SDH (Synchronous Digital Hierarchy) is the standard technology for the information transmission in broadband optical networks. Unlike the Internet, SDH networks are strictly planned; rings, meshes, stars, or tree-branches topologies are designed to connect their basic elements. In spite of that, we have found that the SDH network operated by Telefónica in Spain since 1992, shares remarkable topological properties with other real complex networks. In fact, we have found the fingerprint of the so called complex networks such as power-law scaling in the degree distribution and properties of small world networks [1]. In this communication we present an ad hoc model to describe the complex topology found in the Spanish system. The model considers real planning directives and geographical and technological variables. The topological properties of the networks generated by the model are in good agreement with the Spanish SDH network [2].

[1] J. P. Cárdenas, M. L. Mouronte, A. Santiago, V. Feliu and R. M. Benito “Complex topology in optical transport networks”, International Journal of Bifurcation and Chaos. Submitted.

[2] A. Santiago, J. P. Cárdenas, M. L. Mouronte, V. Feliu and R. M. Benito, “Modeling the topology of SDH Networks”. International Journal of Modern Physics C 19 (2008) 1809-1820.
23: Gergely Palla, Illes Farkas, Peter Pollner, Imre Derenyi and Tamas Vicsek. Statistical features and self-similar properties of tagged networks    (abstract only)   information
Abstract. Submission for contributed talk.

Tagged networks provide a step towards a more complete description of the structure of large complex systems. We present here some relations between the statistical properties of the node tags and those of the graph topology. In order to better characterize the networks with tagged nodes, we introduce a number of new notions, including tag-assortativity (relating link probability to node similarity), and new quantities, such as node uniqueness (measuring how rarely the tags of a node occur in the network) and tag-assortativity exponent. We apply our approach to three large networks of high importance from the aspect of practical applications, capturing the relations between interacting proteins, collaborating scientists, and pages of an on-line encyclopedia. These networks are tag-assortative, but variate in uniqueness.
We find also that for each network the topology and the tag distribution are scale invariant, and this self-similar property of the networks can be well characterized by the tag-assortativity exponent, which is specific to each system.
24: Joel Tenenbaum, H. Eugene Stanley and Shlomo Havlin. Contributed talk: Correlation Networks of Earthquakes    (abstract only)   information
Abstract. Earthquakes are complex spatiotemporal phenomena.  Though seismologists have observed statistical laws, the underlying mechanism governing earthquake events is still not understood, particularly in its spatial dependence.  We propose a novel method for gaining insight into seismic events using networks.  We find that the locations of earthquake events are remarkably interconnected and that such connections stretch over surprising distances.  These distances far exceed the size of traditional fault zones, resulting in consequences for earthquake prediction.
25: Pu Wang, Marta González, César Hidalgo and Albert-László Barabási. Understanding the spreading patterns of mobile phone viruses    (abstract only)   information
Abstract. Mobile viruses are little more than a nuisance today, but given our increased reliance on wireless communication, in the near future they could pose more risk than their PC based counterparts. Despite of the more than three hundred mobile viruses known so far, little is known about their spreading pattern, partly due to a lack of data on the communication and travel patterns of mobile phone users. Starting from the traffic and the communication pattern of six million mobile phone users, we model the vulnerability of mobile communications against potential virus outbreaks. We show that viruses exploiting Bluetooth and multimedia messaging services (MMS) follow markedly different spreading patterns. The Bluetooth virus can reach all susceptible handsets, but spreads relatively slowly, as its spread is driven by human mobility. In contrast, an MMS virus can spread rapidly, but because the underlying social network is fragmented, it can reach only a small fraction of all susceptible users. This difference affects both their spreading rate, the number of infected users, as well as the defense measures one needs to take to protect the system against potential viral outbreak.
26: Sinan Aral, Lev Muchnik and Arun Sundararajan. Influence Dynamics in Large Complex Networks    (abstract only)   information
Abstract. Abstract for Submission of "Contributed Talk"

We use an unprecedented data set and a quasi-experimental research design to examine the extent to which networked relationships explain, and influence patterns of user behavior, product adoption, and online demand.  Our data include (i) a global instant messaging (IM) network of 27 million users from, (ii) detailed data on the day-by-day adoption of Yahoo Go, a mobile service application, and (iii) detailed daily data on nearly all e-commerce actions taken by the same users on Yahoo’s websites. We ask: to what extent do networked relationships influence consumers economic choices, creating systematic patterns in product demand? Two main sources of empirical evidence have been used to substantiate the existence of social contagion or peer influence in large social networks: (i) assortative mixing – the correlation of behaviors amongst linked nodes, and (ii) behavioral (network) autocorrelation – the temporal interdependence of behaviors amongst friends. We find strong evidence of both assortative mixing and behavioral network autocorrelation in our data. Economic decisions “cluster” in networks and time - individuals with friends who adopt the mobile service are much more likely to adopt and adoption decisions amongst friends cluster in time. However, these arguments do not discount the likelihood that homophily – the demographic, behavioral and preference similarity of linked nodes – may indeed explain a good deal of the variance in both assortative mixing and behavioral network autocorrelation that is currently attributed to contagion or peer influence. To separate influence from homophily, we introduce a dynamic matched sample estimation framework, viewing combinations of number of adopter friends, local clustering, relative tie strength and dyadic attribute distance as treatments, and subsequently comparing adoption rates between “treated” and “untreated” consumers. We find that previous methods overestimate the degree of peer influence in large complex networks by up to 500% and that homophily explains a great deal of behavioral contagion. Our methods are replicable and establish upper bounds for estimates of peer influence in large complex networks.
29: Haibo Hu and Xiaofan Wang. How people make friends in online social networking sites?–A microscopic perspective    (abstract only)   information
Abstract. The WWW is undergoing a landmark revolution from the traditional Web 1.0 to Web 2.0 characterized by social collaborative technologies, such as social networking site (SNS), blog, Wiki and folksonomy. As a fast growing business, many SNSs of different scope and purpose have emerged in the Internet, many of which, such as MySpace, Facebook and Orkut, are among the most popular sites on the Web according to Users of these sites form online social networks (OSN), which provide an online private space for individuals and tools for interacting with other people in the Internet. The popularity of these sites and availability of network data sets offer a unique opportunity to study the dynamics of OSNs. Having a proper understanding of how OSNs evolve can provide insights into the network structure, allow predictions of future growth, and enable exploration of human behaviors on networks.

Despite the great progress made by researchers of diverse disciplines in the field of OSN, to date, most analysis of OSNs has focused on the macroscopic statistical properties of static network or multi-snapshot of evolving network rather than detailed microscopic growth dynamics. For the research framework from a macroscopic viewpoint it is usually hard to reveal underlying mechanism and growth processes governing the observed network structure and evolution.

In this paper, based on the empirical data of Wealink - a large SNS in China, we study the detailed process of people making friends from a microscopic point of view. Instead of only focusing on the global network structure or structural metric evolution, we focus directly on the microscopic node behavior per se, i.e. studying the properties of a sequence of individual edge arrivals.

In particular, we study detailed network growth of Wealink with full temporal information by examining individual node arrival and edge creation processes that collectively lead to macroscopic properties of the network.


      We study the reciprocation behavior of users, and find that links are quickly reciprocated in an exponential form. 67.04% of all reciprocal links occurred within 24 hours after the initial link request and 84.25% of launched link requests were accepted within one month (30 days). Besides the degree of inviter or accepter is almost irrelevant to reciprocation time, which is rather counterintuitive.

      All the users during the data collection period can be divided into three classes: active users who created link requests but have never received ones, passive users who received requests but have never launched ones and mixed users who both created and received requests. It is interesting that most users belong to the first two classes (57.54% for active users and 35.27% for passive ones), indicating the evident diversity of user character. Among the mixed users, there exists strong positive correlation between the numbers of times of launching invitations and accepting invitations (The Pearson correlation coefficient is 0.48).

      All links can be divided into four classes, Old−Old, Old−New, New−Old and New−New, where A−B type expresses that initially A users launched link request to B users. The percentages of the four classes of links are 19.39%, 30.28%, 49.13% and 1.19% respectively. The number of edges of Old-Old type is relatively small leading to the sparseness of the network.

      The temporal feature of the online community shows that the distributions of intervals of user behaviors, such as launching and accepting link requests, follow power law with a universal exponent 1.89, and peaks with intervals of integral day appear in the tail of the distributions.

      We study the preferential selection and attachment phenomena of Wealink and find that linear preference holds for both cases, which can collectively result in the power law distribution of users’ activity and popularity (Simon model), and the power law degree distribution of the network respectively.

The research framework from a microscopic perspective can provide a potential insight into how the micro-motives of web users lead to the global structure of OSNs


We thank Wealink Co. for providing the network data. This work was partly supported by the NSF of PRC under Grant No. 60674045.
30: Ying Fan and Zengru Di. Insight to the Express Transport Network    (abstract only)   information
Abstract. (for a contributed talk)

The express delivery industry is developing rapidly in recent years, and has attracted attention in many fields. Express shipment service requires that parcels be delivered in a limited time with a low operation cost, which requests a high level of ecient express transport network (ETN). The ETN is constructed based on public transport networks, especially the airline networks, but it has its own feature. With the complex network theory, the statistical properties of the ETN are analyzed deeply. We find that the ETN has the small world and scale free properties, with disassortative mixing behavior and rich club phenomenon, It also shows di erence from the airport network in some features, such as edges density and average shortest path. The reason for the di erence maybe that the ETN cares about the tradeo between time eciency and cost, while the airport network care more about convenience for customers. At last, an evolving model,which takes both geographical constraints growing and preference attachment into account, is proposed .The model shows similar properties with empirical results.
31: Fabrizio Natale, Lara Savini, Diana Palma, Paolo Calistri, Armando Giovannini, Possenti Luigi, Zippo Daniele and Gianluca Fiore. Network based tools for tracing livestock movements in the case of disease outbreaks    (abstract only)   information
Abstract. Data about animal movements and the resulting contacts between holdings can be represented in the form of networks where the premises of origin and destination of the movement are defined as nodes and the movements of animals between premises are defined as relations or edges connecting the nodes.
Several studies in the veterinary sector have demonstrated how the spread of diseases can be determined by the nature and structure of these contact networks. The network-based approach is an alternative to the classical modelling of disease based on a geographical dimension. In the network of animal movement the spreading path is independent from geographical location and distances and rather linked to the structure of the network and the topological role of premises within the network, which can be described through several centrality measures, derived from network analysis methodologies.
A system has been developed to extract movement data from the National Italian Bovine Database using web services technology and dynamically explore the resulting networks using a local application for network visualization. This tool gives the possibility to quickly and more efficiently identify the possible origin or destination of the infection in the course of a disease outbreak.
The application includes functionalities to simulate the disease spread using a meta-population epidemic model. The spread of the disease is simulated by using a homogeneous mixing assumption within each sub-population and by taking into account the network structure and the intensity of the interactions when the spread of the disease among sub-population is considered.

Type of submission: Contributed talk

Field: Networks in Health & Society
32: Jun Wu, Yuejin Tan and Hongzhong Deng. Model for Invulnerability of Complex Networks with Incomplete Information based on Unequal Probability Sampling    (abstract only)   information
Abstract. (For contributed talk). To bridge the gap between random failure and intentional attack, considering the process of acquiring attack information as the unequal probability sampling, a novel model for invulnerability of complex networks with incomplete attack information is proposed, in which the attack information can be controlled by a tunable attack information accuracy parameter and a tunable attack information range parameter. The known random failure and the intentional attack are two extreme cases of our model. Using the generating function method, the analytical expressions of the critical removal fraction of vertices for the disintegration of networks and the size of the giant component under two special cases of incomplete attack information, i.e. random information and preferential information are derived, which allow us to make predictions on the invulnerability of complex networks under attack with incomplete information. Taking scale-free networks for example, the invulnerability of complex networks with general incomplete attack information is studied numerically. It is shown that hiding just a small fraction of vertices randomly can enhance the invulnerability and detecting just a small fraction of important vertices preferentially can reduce the invulnerability.
33: Jun Wu, Yuejin Tan and Mauricio Barahona. Robustness of Regular Graphs Based on Natural Connectivity    (abstract only)   information
Abstract. (For contributed talk ) The concept of natural connectivity has recently been proposed to measure the robustness of complex networks. The natural connectivity characterizes the redundancy of alternative routes by quantifying the weighted number of closed walks of all lengths and can be derived mathematically from the graph spectrum as an average eigenvalue. In this paper, we explore the natural connectivity of regular graphs both analytically and numerically. We first employ the generalized Bessel function to show that the natural connectivity of regular ring lattices, in which each vertex is connected to its nearest neighbors, is independent of network size and increases with monotonically. Then we investigate the natural connectivity of random regular graphs by random degree-preserving rewiring starting from regular ring lattices. We find that random regular graphs are less robust than regular ring lattices based on natural connectivity.
34: Rui Carvalho, Lubos Buzna, Flavio Bono, Eugenio Gutierrez, Wolfram Just and David Arrowsmith. Robustness of Trans-European Gas Networks: The Hot Backbone    submission   information
Abstract. Here we uncover the load and vulnerability backbones of the Trans-European gas pipeline network. Combining topological data with information on inter-country flows, we estimate the global load of the network and its vulnerability to failures. To do this, we apply two complementary methods generalized from the betweenness centrality and the maximum flow. We find that the gas pipeline network has grown to satisfy a dual-purpose: on one hand, the major pipelines are crossed by a large number of shortest paths thereby increasing the efficiency of the network; on the other hand,
a non-operational pipeline causes only a minimal impact on network capacity, implying that the network is error-tolerant. These findings suggest that the Trans-European gas pipeline network is robust, i.e. error-tolerant to failures of high load links.
35: Di Zengru and Ying Fan. Scaling Properties in Spatial Networks and its Effects on Topology and Traffic Dynamics    (abstract only)   information
Abstract. For Contributed Talk

Empirical studies on the spatial structures in several real
transport networks reveal that the distance distribution in these
networks obeys power law. To discuss the influence of the power-law
exponent on the network's structure and function, a spatial network
model is proposed. Based on a regular network and subject to a
limited cost $C$, long range connections are added with power law
distance distribution $P(r)=ar^{-\delta}$. Some basic topological
properties of the network with different $\delta$ are studied. It is
found that the network has the smallest average shortest path when
$\delta=2$. Then a traffic model on this network is investigated. It
is found that the network with $\delta=1.5$ is best for the traffic
process. All of these results give us some deep understandings about
the relationship between spatial structure and network function.
36: Jun Wu, Yuejin Tan and Mauricio Barahona. Robustness of Random Graphs Based on Natural Connectivity    (abstract only)   information
Abstract. (For contributed talk ) The concept of natural connectivity has recently been proposed to measure the robustness of complex networks. The natural connectivity has a clear physical meaning and can be derived mathematically from the graph spectrum as an average eigenvalue. In this paper, we explore the natural connectivity of random graphs both analytically and numerically. We show that it increases with the average degree linearly. By comparison with regular ring lattices and random regular graphs, we show that random graphs are more robust than random regular graphs, but the relationship between random graphs and regular ring lattices depends on the average degree and graph size. We find a critical graph size as a function of average degree, which can be predicted by our analytical results. When the graph size is less than the critical value, random graphs are more robust than regular ring lattices, whereas regular ring lattices are more robust than random graphs when the graph size is greater than the critical value.
37: daqing li and shlomo havlin. Overlapping Synchronization    (abstract only)   information
Abstract. The complex network structure has been found in many realistic systems[1].  Modularity of network (cluster), which has dense intra-connection inside and sparse interconnection between clusters, is used to explain the system function [2]. However, there usually are some overlapping structures between clusters which could be hardly partitioned to any single cluster. These overlapping clusters also play an important role in the dynamics on the complex modularity network [3]. In this paper, we mainly focus on synchronization on the overlapping structure.  With Kuramoto model, we implement different natural frequency to different cluster to check how the overlapping cluster synchronizes with these clusters. It is found that with different natural frequency, the synchronization pattern of overlapping cluster could be significantly different.  The result could shed some light on the understanding of how different biological functional motifs communicate.

In this study, the  Kuramoto model[4] is invoked to  study the  synchronization.  The node could only be directly influenced by the other connected nodes.  The network is composed of two giant clusters(ER) with different natural frequency distribution and an overlapping cluster.  The connection between two giant cluster and overlapping cluster is symmetric.  We will study the synchronization frequency of each cluster.

When coupling is weak, with different mean natural frequency, synchronization pattern of overlapping cluster would significantly. If the mean natural frequency equals to the mean frequency of  the other two cluster, the  real frequency oscillates symmetrically between the two clusters(Overlapping synchronization, Fig. 1).  However, when the natural frequency is closer to that of cluster A, the real frequency is more attracted by cluster A.

The Overlapping cluster could be regarded as coupled by mean frequency of the other two cluster.  If the coupling is strong enough, the effect would be more significant.  So long as the cluster(node) is overlapping structure,  it would be frequency locked by mean field frequency.  The closer natural frequency is from the mean field frequency, the more locking time is.

If the connections from two cluster to overlapping cluster are asymmetrical. The locking frequency is also asymmetrically distributed between the other two.
38: M. Ángeles Serrano. Rich-club vs rich-multipolarization phenomena in weighted networks    (abstract only)   information

Large-scale hierarchies characterize complex networks in different domains. Elements at the top, usually the most central or influential, may show multipolarization or tend to club together, forming tightly interconnected communities. The rich-club phenomenon quantified this tendency based on unweighted network representations. Here, we define this metric for weighted networks and discuss the appropriate normalization which preserves the nodes’ strengths and discounts structural strength-strength correlations if present. We find that in some real networks the results given by the weighted rich-club coefficient can be in sharp contrast to the ones in the unweighted approach. We also discuss the ability of the scanning of weighted subgraphs formed by the high-strength hubs to unveil features in contrast to the average: the formation of local alliances in multipolarized environments, or a lack of cohesion even in the presence of rich-club ordering. Beyond structure, this analysis matters for correct understanding of functionalities and dynamical processes relying on hub interconnectedness.

M. Ángeles Serrano, PHYSICAL REVIEW E 78, 026101 (2008)
39: Andrea Lancichinetti and Santo Fortunato. Benchmark graphs for community detection algorithms    (abstract only)   information
Abstract. Community structure is one of the most important features of real networks and reveals the internal organization of the nodes. Many algorithms have been proposed but the crucial issue of testing, i.e., the question of how good an algorithm is, with respect to others, is still open. Standard tests include the analysis of simple graphs adopted in actual tests have a structure that does not reflect the real properties of nodes and communities found in real networks. We introduce a new class of benchmark graphs (for binary, directed and weighted networks), that account for the heterogeneity in the distributions of node degrees and of community sizes. We use this benchmark to test two popular methods of community detection, modularity optimization, and Potts model clustering. The results show that the benchmark poses a much more severe test to algorithms than standard benchmarks, revealing limits that may not be apparent at a first analysis.
40: Jose Marcelino and Marcus Kaiser. Controlling spreading: Improved strategies for airline, social, and neural networks using edge removal.    (abstract only)   information
Abstract. We would like to submit the following abstract for a contributed talk.

Recent empirical data of real-world networks, from human travel and collaboration networks to neural and cortical connectivity, has facilitated more realistic studies of epidemic spreading.  Previous work on spreading of diseases via the airline network and of computer viruses through the Internet has suggested that removing highly connected nodes (hubs) is an effective control strategy. We will revisit this assumption as well as present alternative strategies using edge removal on social and neural networks both at the global scale (airline and macaque cortical network) and the local scale (Jazz musician collaboration and C. elegans neuronal network).  
Our results reveal that three out of four edge removal measures are consistently better than hub removal for these networks (i.e. the same spreading slowdown is obtained while removing fewer edges). Spreading via the airline network, for example, would take up to 29% longer if an equally sized set of selected flights were cancelled instead of closing down whole airports.
In addition, we discuss how removal strategies differed in their impact on dynamic (spreading time) and structural (global efficiency) features. The performance of a measure in affecting network structure was a poor predictor of its impact on slowing down dynamic spreading.
In conclusion, our work shows that edge removal strategies provide a more efficient spreading control in a wide range of natural networks.
41: Fabio Caccioli and Luca Dall'Asta. Non-equilibrium mean-field theories on scale-free networks    (abstract only)   information
Abstract. Submission for a contributed talk.

Random graphs are the natural framework where to study the influence of topology on the physical properties of complex systems.  It is of primary importance to develop theoretical tools that can be used when dealing with complex networks.
The study of dynamical processes on random graphs is often carried out trough mean field approaches, which in complex topologies are expected to give a good characterization of the system, since the absence of spatial fluctuations.
Deviations from the expected mean-field predictions have however been observed in some reaction diffusion processes on scale free networks and a debate about the effectiveness of such methods has been recently raised.
We propose a general mean field theory  for non equilibrium processes on scale free networks, collecting in an unifying framework concepts previously introduced for very specific problems.
The approach allows to easily derive Langevin equations for mean-field order parameters that implicitly account for the degree heterogeneity and can be used to correctly predict the critical behavior of different classes of models. Moreover it can be considered as the generalization of the Landau Ginzburg theory to non equilibrium processes on complex networks.
The method is successfully applied to the voter model, the Glauber dynamics and reaction diffusion processes.
In particular we can easily show that the nature of the critical behavior depends on the cutoff of the degree distribution. For finite cutoff the system eventually recovers the homogeneous mean field behavior, while networks with infinite cutoff present a critical behavior that depends on the exponent of the degree distribution.
The method allows also to understand how fluctuations due to the noise can
affect single realizations of the process.
42: Stefania Vitali, James Glattfelder and stefano battiston. The Network of Global Corporate Control    (abstract only)   information
Abstract. Ownership networks are prominent examples of complex economic networks
  in which the value of firms as well as the control of firms over other
  firms flow through all the paths in the graph. An ownership network is
  shaped by the interplay of opposing economic interests and its
  structure has implications for economic competition in the market. In
  this work, we present the very first study of the global network of
  transnational corporations (TNCs) world-wide. The nature of nodes and
  edges in the system requires to go beyond the typical complex network
  measures. By combining the topological analysis with the computation of
  indirect control flow together with a geographical analysis, we show a
  number of relevant facts which were previously unreported. In
  particular, we find a bow-tie structure with a small but very dense
  (strongly connected) core which accumulates most of the control over
  all the TNC value world-wide. The majority of the firms in the core
  belong to the financial sector and are located in US and
  EU. Remarkably, a large extent of the network control over the core
  remains within the core itself, thanks to many mutual direct ownership
  relations as well as longer cycles. Overall, the network control is
  highly concentrated with less than 1% of TNC and their shareholders holding
  80% of the whole control. The results show that an appropriately
  designed analysis of a complex network can contribute significantly to
  research questions on socio-economic systems. Our approach can be
  adapted to many other large-scale economic and social networks.
43: stefano battiston, Domenico Delli Gatti, Mauro Gallegati, Joseph Stiglitz and Bruce Greenwald. Liaisons Dangereuses: Increasing Connectivity, Risk Sharing, and   Systemic Risk.    (abstract only)   information
Abstract. In order to investigate the relations between the structure of financial networks and their resilience
to global crises, we model the propagation of financial distress and the process of bankruptcy cascades on a graph.
In particular, we characterize the evolution over time of a credit network as a system
  of coupled stochastic processes, each one of which describes the
  dynamics of individual financial robustness. The coupling comes from
  the connectivity of the network, since each agents' financial
  robustness is associated with the financial robustness of the partners
  through risk sharing, distress propagation and the bankruptcy cascade
  effects. In this framework we consider the effects of a shock to a
  specific node as network connectivity increases. Under specific
  conditions, we detect the emergence of a trade off between
  decreasing individual risk -- due to risk sharing -- and increasing
  systemic risk -- due to the propagation of financial distress.  The
  larger the number of connected neighbors, the smaller the risk of an
  individual collapse but the higher systemic risk. In other words, the
  relationship between connectivity and systemic risk is
  not monotonically decreasing as usually found in the literature. Risk
  sharing by itself would lead systemic risk to zero as the
  connectivity increases. Instead, distress propagation and the bankruptcy cascade
  effect, together with trend reinforcement -- i.e. the fact that
  individual financial fragility feeds back on itself-- may amplify the
  effect of the initial shock and lead to systemic crises if they more than offset risk sharing.
44: Andrea Baronchelli, Michele Catanzaro and Romualdo Pastor-Satorras. RANDOM WALKS ON COMPLEX TREES    (abstract only)   information
Abstract. (submission for a Contributed Talk)

Diffusion problems on tree structures pop up in a wide range of
scientific domains, such as theoretical physics, computer science,
phylogenetic analysis and cognitive science. Recently, however, an
increasing number of studies have reported that many dynamical models
exhibit peculiar behaviors when the underlying structure is a tree
rather than a looped network.

Here we focus on random walks on complex finite trees. Compared to
looped structures, we find that the global constraint of lack of loops
induces a general slowing down of diffusion, as measured by the
network coverage and the mean topological displacement from the
origin. As well, it profoundly alters the degree dependence of the
mean-first passage time (MFPT). Indeed we show that in trees the
source-target distance is the dominating parameter, rather than the
target degree. We therefore study a symmetrized MFPT and derive an
analytic expression of its logarithmic dependence on degree, obtaining
good agreement with simulation results.

Taken as a whole, our results concerning the elementary random walk
help to shed light on the anomalies observed in diffusive dynamical
systems on trees.

A. Baronchelli, M. Catanzaro and R. Pastor-Satorras, "Random walks on
complex trees", Phys. Rev. E 78, 016111 (2008).
45: Gergely Palla, Tamas Vicsek and Laszlo Lovasz. A General Graph Generator    (abstract only)   information
Abstract. We introduce a new approach to constructing networks with realistic features based on multifractals. Our method, (in spite of its conceptual simplicity) is capable of generating a wide variety of networks with prescribed statistical properties, e.g., with  degree or clustering  coefficient distributions of various, very different forms. In turn, these graphs can be used to test hypotheses or as models of actual data.
46: Renaud Lambiotte, Jean-Charles Delvenne and Mauricio Barahona. Laplacian Dynamics and Multiscale Modular Structure in Networks    (abstract only)   information
Abstract. The complex structure of many social, information and biological networks is underpinned by communities at different scales. These topological modules are often indicative of underlying features and functionalities, such as tightly-knit groups of metabolites or species in biological networks. The presence of well-defined communities also has an effect on the dynamics taking place on a network. A variety of methods and measures have been proposed to uncover these modules, most notably modularity and spectral partitioning. However, these approaches are based on structural, static properties of the network. Here we introduce a definition for the quality of the partition of a network that is based on the statistical properties of a dynamical process taking place on the graph. This measure, denoted the stability of the partition, has an intrinsic dependence on the time-scale of the process, which can be used to uncover community structures at different resolutions. The stability extends and unifies standard community detection algorithms. In particular, both modularity and spectral partitioning are shown to have a dynamical interpretation in the case of undirected networks and can be seen as limiting cases of the stability. Similarly, several multi-resolution methods correspond to linearisations of our measure at short times. In the case of directed networks, however, stability differs from modularity by its non-local nature as it is based on the persistence of probabilistic flows in modules. We apply our method to find multi-scale partitions for different examples and show that the stability can be computed efficiently through the use of extended versions of current algorithms that can deal with large networks.

This submission is for a contributed talk.
The talk is based on the paper arXiv:0812.1770
47: adolfo paolo masucci, Duncan Smith, andrew crooks and michael batty. Random planar graphs and the London street network    submission   information
Abstract. In this talk we analyse the street network of London both in its primary and  dual representation. To understand its properties we consider a grid model, a static planar graph model and we introduce a growing random planar graph model. By the comparison between the models and the street network we find that the streets of London are a self-organised system whose growth is characterised by a strict interaction between the metrical and informational space. In particular a principle of least effort seems to apply to create a balance between the physical and the mental effort to navigate the city.
48: C.-K. Yun, N. Masuda, C. Choi and Byungnam Kahng. Aggregation and condensation of dynamic clusters on complex networks    (abstract only)   information
Abstract. Recently, dynamic problems on complex networks such as the Prisoner's Dilemma (PD) game have drawn considerable attention from diverse disciplines. The PD game is an evolution model describing mutual interactions among individuals in society. It was shown that cooperation is enhanced on random scale-free (SF) network compared with in the Euclidean space due to the presence of hubs. Connected hubs in SF networks form a skeleton of cooperators, which is robust against invasion by defectors. In this paper, we show that when SF network is fractal, such behavior does not occur and cooperators form isolated clusters. The size distribution of isolated clusters exhibits a power-law behavior. The transition between two behaviors seems to be of interest, of which the detail is under progress. Similar behavior can be found in other dynamic problems such as the evolution of spin domains in the Ising model.
49: Vasco M. Carvalho. Structure and Change in U.S. Commodity Networks    (abstract only)   information
Abstract. I use the theory of complex networks to characterize the flows of commodities among different sectors in the US economy. By using product line data from the US Census and sector to sector transactions from detailed Input-Output tables, I show that, over the last 40 years: i) the sales of narrowly defined commodities exhibit a robust scaling of the Pareto type; ii) that sectoral forward linkages also follow a Pareto distribution; iii) that sector to sector commodity networks are small worlds with short characteristic path length and low diameter; iv) that, similarly to other technological networks, commodity networks exhibit negative assortativity and high clustering coefficients. The paper concludes by zooming in on the network dynamics of IT and IT-intensive sectors, providing an analysis of the evolution of these sectors and the rise of IT centrality in the US economy.

50: Jennifer Simonotto, Stephen Eglen, Marcus Kaiser, Christopher Adams and Evelyne Sernagor. Analysis of spontaneous activity patterns in developing retina: extracting and analyzing dynamical networks    (abstract only)   information
Abstract. This submission would be for a potential contributed talk.

As part of a recent consortium (CARMEN - Code, Analysis Repository and Modeling for E-Neuroscience), we investigated the spatiotemporal activity and resulting dynamical networks of retinal waves using spike times extracted from multi-electrode array (MEA) recordings taken at different labs at corresponding ages in development of different genetic strains of mice. We describe several measures for assessing changes in network topology both over time and between different recordings. As the recording electrodes and the underlying structural neural network extends in two-dimensional space, we also present methods for assessing the direction and spreading of activity (retinal waves) in neuronal networks.  Spike time data was quantified using network analysis measures (degree, jaccard coefficient, page rank, etc), as well as more traditional MEA measures such as burst analysis, frequency changes and wave characteristics. More analysis methods will be implemented in the future and compared with existing results, with the final aim to correlate and compare many result ‘frames’ with each other, extracting more complete information regarding underlying network structure of during/between wave and burst activation. The CARMEN infrastructure allows us to store and analyze these large data sets in a consistent manner. All tools will be available in the near future through the CARMEN portal (
This study is part of the CARMEN Consortium Work Package 6 investigating small neural networks dynamics. We thank the CARMEN Consortium for their support. (EPSRC:EP/E002331/1)
51: Steve Uhlig and Almerima Jamakovic. On the trade-off between efficiency and robustness in communication networks    submission   information
Abstract. As users of communication networks, we are mostly concerned with our experience of the network. Users are oblivious to the huge investment in time and resources necessary to reach a high quality of experience. At the interface between the user and the network, communication protocols do their best in order to minimize the impact of faults on user experience, so that the network is as transparent
as possible to the user. While network protocols can help reaching optimal user experience, they do not compensate for poor network topology design, e.g. the existence of bottlenecks or broken connectivity in case of failures.

Communication network design is a multiple objective problem, where efficiency and availability must be maximized even under complex failure scenarios. Additionally, those goals must be achieved at reasonable costs. Rules of thumb and heuristics are most commonly used by network engineers. These heuristics rely only on very simple topological properties of graphs, e.g. bi-connectivity. As a result, communication networks are typically made of interconnected tree, ring and grid structures that trade-off efficiency, resilience, and cost. As we show in this paper in the case of real-world communication networks, with more complex network structures, this trade-off between efficiency and robustness is more fuzzy.
52: Stefan Hennemann. Measuring regional scientific knowledge flows – Contributions of spatial sub-units to the networking performance of metropolitan regions    (abstract only)   information
Abstract. - Abstract for contributed talk -

The development capabilities of regional economies depend on many internal and external factors. One of those factors is the ability to absorb and to utilize internally and externally created knowledge. This is both prerequisite for and outcome of socio-economic activity and can be treated as an independent factor to enable sustainable growth in knowledge-based economies.
Metropolitan regions (MR) are the ideal locus of catalyzing knowledge, as they provide several crucial ingredients and a critical mass of resources (e. g. availability of human capital, soft location factors, specialized corporate functions and external services, early adopters) to support knowledge creation and, eventually, induce innovation. However, MR are less single-core agglomerations that provide urbanization and localization advantages. Today, most MR are comprised of polycentric structures, which are built upon functional relations between the sub-cores.
So far, this functional cohesion has not been sufficiently analyzed and the contributions of spatial sub-units to the performance of the whole metropolitan region remain largely uncharted. Measuring networking capabilities and activities with respect to regions is a difficult task due to at least three major potential issues:

1)Network completeness and sampling (cp. Newman 2003, Canter and Graf 2008)
2)Aggregation and spatial level of investigation (cp. Taylor 2008, Hall and Pain 2006)
3)Size and scaling effects (cp. Bonacich et al. 1998)

To unravel the functional relations in and between metropolitan regions a simple modification of centrality measures is proposed. ‘Regional Closeness’ (i.e. centrality of a regional sub-net of nodes defined by the spatial affiliation to a specific region and all directly connected extra-regional entities) and ‘Inner Strength’ (i.e. defined as the relation of Regional Closeness for intra-regional and extra-regional nodes) are tested with bibliographic data from the Thompson Scientific indices with two German metropolitan regions, Frankfurt/Rhine-Main and Hanover-Braunschweig-Gottingen-Wolfsburg. Additional applications have been made with data of different regional aggregate levels (city, region, federal states/provinces) as well as from different economic development stages (Germany, China). All results can be rationally interpreted.
These regionalized results can be further integrated into, for example regional production functions at different regional scales as the regionalization is not limited to a specific type of region, but can be customized to be congruent to other available data from secondary statistics. This has the potential to estimate the capabilities of endogenous innovation capacities more accurately.
Interestingly, ‘Regional Closeness’ and ‘Inner Strength’ are highly correlated with each other, meaning that the centrality of sub-regions is largely determined by the importance of organizations from the sub-region itself, rather than depending also on influential external nodes. With decreasing importance of a sub-region this behavior reverses. This non-trivial finding deserves further investigation.
53: Pan Hui, Nishanth Sastry, Steve Uhlig and Jon Crowcroft. LENS: LEveraging Network Science to Identify Malicious Users in Communication Networks    submission   information
Abstract. [contributed talk]Spam emails is the most serious kind of unsolicited messaging. There were 1:3 billion email users worldwide in 2008, with 210 billion emails sent per day. Out of all these emails, 70% were spam emails, which accounts to 53.8 trillion of spam emails in 2008. This is a huge number of emails, it causes a lot of inconvenience to solicit users and costs the operators a lot of money on operating expenses to detect and filter spam. In this paper, we leverage network science to develop decentralised algorithms for each individual user to identify its own communities and overall isolate the malicious clusters, including spam and attacks.
54: Bin Liu, Ton Coolen, Xiaoyue Wu and Hongzhong Deng. Robustness of semi-directed networks    (abstract only)   information
Abstract. We study the vulnerability of network connectivity after removal of a fraction q=1-T of edges under the assumption that there are both directed edges and undirected edges in the network. The number of directed edges is M1=M*p , where M is number of all edges and p is semi-parameter. Using the probability generating function method, we find a new percolation transition at Tc for a large class of semi-directed networks, which is relative to semi-parameter p. Above Tc, S nodes can communicate along the direction of edges, while below Tc, semi-directed networks break down and almost any two nodes can not communicate. To validate our model and method, we perform simulations and the simulations meet well with the result of analysis. We also show that undirected edges have an important effect on the robustness of semi-directed networks.
55: Luis Enrique Correa da Rocha and Petter Holme. Assessing sexual networks of prostitution from a web community    (abstract only)   information
Sexually transmitted diseases (STDs) are a major issue of public health. Several studies points out the importance, at least in some cultures, of commercial sex in the spreading of STDs. It is also known that the structure of a network is an important factor in the disease dynamics. Constructing empirical data sets of the commercial sexual networks is hampered by the covert nature of the prostitution. An indirect way of studying such networks is to use data extracted from a web community aimed to provide exchange of information between sex-buyers. Using data only visible online without logging in, we obtain a temporal network of claimed sexual contacts. We construct a bi-partite network by assigning nodes to users and escorts, and connecting them in case a user posts about an appointment with a specific escort. Our study suggests a network dynamics influenced by the commercial nature of the activity. Although only the users are able to post, the positive feedback from other users through previous posts (appointments) has an effect to attract more customers to certain escorts. We also study the geographical aspect -- people within a city are highly interconnected and though most of the nodes belong to the giant component, few but important edges connect different cities. We, furthermore, investigate the effects of the network structure on disease spreading by using the susceptible-infected epidemics model. Constraints from the temporal ordering of contacts slow down the disease spreading and accentuate the importance of the initial condition on the disease dynamics. Our results indicate that some people are regularly active and the removal or vaccination of 3% of the most active users reduces the projected outbreak size by a factor of ten.
56: Alexander Mehler. A Quantitative Graph Model of Social Ontologies    (abstract only)   information
Abstract. [Paper]

A social ontology is the output of a sort of social tagging which came into existence with the web 2.0. It emerges as a solution to a coordination problem among large groups of interacting agents (Bickhard 2008). This relates to the sharing of a collectively structured semantic universe (Steels 2006) in the form of ontological structures (Sowa 2000). Unlike mass communication (as a kind of one-to-many communication) a social ontology results from a many-to-many communication in which groups of agents interact to constitute and organize a dynamically growing universe of content units.

In this paper we answer the question whether natural languages can be distinguished by the topology of their social ontologies represented as complex networks with a DAG-like kernel. This research question relates to the so called Sapir-Whorf hypothesis (Whorf 1956). It says that there is a systematic relation of the grammatical and lexical categories of a language and the way its speakers represent the world. The Sapir-Whorf hypothesis combines the principle of linguistic determinism with that of linguistic relativity. It is the latter to which we subscribe. According to this view, languages with similar grammatical and lexical systems (i.e., languages of the same family) should also be similar in their semantic representations of the world. Thus, by analyzing semantic systems which are generated in different languages we should be informed about the relatedness of these languages. It is this hypothesis which we test by example of social ontologies as a sort of semantic systems. To say it in terms of a dictum of Firth: we show to which degree you shall know the family relation of a language by the social ontology it spans. That is, we provide a graph model with a kernel DAG-like structure as a reliable input to classifying social ontologies and exemplify this in the area of language typology.

In order to test this model, we analyze 160 social ontologies by example of the category graphs of the language specific releases of the Wikipedia. As a pretest of our network model we show that it is expressive enough to classify the various types of ontologies studied as knowledge systems in information science. This relates to formal, standardized and terminological ontologies in relation to social ontologies. All in all, we analyze 190 ontologies and prove that they can be reliably classified in terms of their topology, that is, in purely structural terms. From a methodological point of view, the paper integrates quantitative linguistics with complex network theory. Starting from web-based communication, it spans an interdisciplinary perspective on complex networks. This is done by means of a novel model of hierarchical structure formation in terms of generalized directed nearly-acyclic graphs which is additionally provided by the paper.
57: Anthony Johnson and Marc Anthony Johnson. Longitudinal Analysis of a Chess Match    (abstract only)   information
Abstract. Empirical longitudinal networks are necessary for developing methods for analyzing networks over time.  Of particular interest are those relationships which exhibit dynamic behavior in that they change over some defined time interval.  We model the direct influence relationship among pieces in a chess match.  The chess network is monitored over time as relationships evolve throughout the progression of a game.  Using each player move as a segment of time we will analyze each decision by perspective players as changes to a physical bounded network which has 32 nodes representing individual chess pieces located on an 8 by 8 square board.  The undirected links to the individual nodes are determined by whether or not any two pieces influence the same physical location on the board. Using social network analysis, we explore possible improved chess strategy and highlight theoretical implications for longitudinal network analysis and artificial intelligence.
58: Ian McCulloh and Jonathan Siskey. Network Topology Effects on Correlation between Centrality Measures    submission   information
Abstract. An important difference between network science and traditional methods of analysis is the focus on structure in relational data.  In some cases, structural properties may hold greater explanatory power for various application areas than attribute variables.  There exist many different structural properties in network science, with various centrality measures being most prevalent.  The degree to which these measures are correlated is therefore important in determining which measures are redundant and which measures may offer new insight into the structural behavior of a network.  Furthermore, the topology of the network structure may affect the degree to which certain measures are correlated.
We propose a network simulation approach that creates networks with varying degrees of Erdos-Renyi randomness and Albert-Barabasi scale-freeness.  Using this simulation approach we conduct 10 replications of a full factorial experimental design with varying levels of density and randomness versus scale-freeness.  The correlations of degree, betweenness, closeness, and Eigenvector centrality are investigated for the effects of topology and density.
Some network centrality measures exhibit high levels of correlation.  The density and topology of the network are statistically significant factors for the level of correlation in all combinations of the investigated measures except the correlation of degree and eigenvector centrality.  Only the density of the network appears to significantly affect this correlation.  Finally, networks with Erdos-Renyi randomness tend to have higher levels of correlation between centrality measures.
59: Ian McCulloh, Joshua Lospinoso and Natalia Mendoza. Actor-Oriented Specification to Validate Simulation of Complex Networks    submission   information
Abstract. Actor-oriented specifications in complex networks presume that nodes will make choices of which alters to connect with based on some derived utility, such as preferential attachment, reciprocity, transitivity, or other factors.  In some cases constraints may be imposed upon the ability of node to connect with alters.   It has been demonstrated that both the statistically significant factors of utility and the constraints may vary among different empirical network data (Lospinoso, McCulloh, AISB 2009).  
     We propose that empirical networks can be effectively modelled with multi-agent simulation when the model is properly validated.  Actor-oriented specifications can be estimated with pseudo-maximum likelihood.  The mathematical model of statistically significant factors affecting network behaviour can be used to drive nodal interaction in a multi-agent simulation.  This approach is demonstrated on a data set consisting of the email activity among 82 individuals at the U.S. Military Academy.  The social interaction of these individuals is modelled in a multi-agent simulation.  Changes due to events such as home football games or academic requirements are also introduced based on observed changes in actor-oriented specifications in the empirical data.  This work represents a significant step forward in developing predictive models of network behaviour.
61: Soon-Hyung Yook and Yup Kim. Percolation transition of the synchronized cluster on complex networks    (abstract only)   information
Abstract. -- submission for Contributed talk

We investigate the percolation transition of the Kuramoto model on complex networks to understand how the largest synchronized connected component (LSCC) is formed and evolves to achieve a globally synchronized state. For the theoretical purpose, we use two different networks, Erd{\"o}si-R{\'e}nyi network and Barab{\'a}si-Albert network. Using the finite-size scaling analysis, we find that the scaling exponents for the percolation order parameter and mean cluster size on both networks agree with the mean-field values, $\beta=\gamma=1$. We also find that the finite-size scaling exponent, $\bar\nu$, also agrees with the mean-field percolation result, $\bar\nu=3$. Moreover, we also show that the cluster size distributions are identical with the mean-field percolation distribution on both networks. Combining with the analysis for the merging clusters, we directly show that the LSCC on both networks evolves by merging clusters of various sizes.
62: Yeo-Kwang Yun, Sung-Min Lee, Soon-Hyung Yook and Yup Kim. Effect of degree correlation to the statistical properties of sampled networks    (abstract only)   information
Abstract. -- submission for a poster --

We study the effect of the degree correlation on the statistical properties of  sampled networks based on a dynamical properties of biased random walk. From the numerical simulations, we find that the biased random walk sampling well inherits most of the topological properties of the original networks compared to the unbiased random walk sampling when the Pearson coefficient for degree correlation is large. Moreover, we find that the functional dependence of the clustering coefficient on degree $k$, $C(k)$, is preserved very well in the sampled networks when both the strength of biased walk and Pearson coefficient increase. This indicates that the modular structure of the original network can be preserved very well if we use the biased random walk sampling. We discuss the relationship between dynamical properties of biased random walks and network sampling.
63: HYUNG JUN PARK. Self-Organizition, Collaborative Regional Governance and Network    (abstract only)   information
Abstract. How local jurisdictions organize governance in metropolitan areas to resolve
collective action problems has been a contentious issue in urban politics and policy. How local jurisdictions organize governance in metropolitan areas to resolve
collective action problems has been a contentious issue in urban politics and policy. While advocates of regionalism argue for the necessity of metropolitan government in order to address externalities and scale problems along with distributional inequalities, and coordination problems (Downs 1994; Lowery 2000), the supporters of metropolitan governance maintain that decentralized units of governments are capable of selforganizing and to resolve these issues more efficiencely.
  The study of urban governance, hence, needs to focus not just on who
governs but also on how, particularly the mechanisms that multiple jurisdictions in
metropolitan areas utilize to coordinate their actions in order to address problems that are increasingly interconnected. A governance perspective focuses on nnetworks constructed from the bottom up through processes of local interaction among local political entities rather than designed
64: Eiko Yoneki and Jon Crowcroft. GIS: Geographical Information Cascade in Online Social Networks    (abstract only)   information
Abstract. *** contributed talk ***

Network shared User Generated Content (UGC) is increasingly popular due to the emergence of Web 2.0.  YouTube videos are an example, where the popularity of videos is driven by viewers and their popularity can vary dynamically and often dramatically. Access to the web containing UGC is known to follow a heavy-tailed distribution. For example, the top 10% of the videos in a normal video-on-demand system account for approximately 60% of accesses, and the rest of the videos (the 90% in the tail) account for 40%.

Thus, traditional content caching and distribution algorithms for web data are not efficient for UGC, since they are optimised for globally popular content. We need a new way to predict which contents will become popular so that the dynamics of popularity can be modelled.

In this talk, we show that information encoded in social network structure can be used to predict access patterns which may be partly driven by viral information dissemination, termed as a social cascade. Specifically, knowledge about the number and location of friends of previous users is used to generate hints that enable placing replicas closer to future accesses.

In general, knowledge of UGC can spread in two ways: broadcast highlights or viral propagation. The rest happens when the UGC object is featured or highlighted on a central index page. Examples include being featured on the home page of the hosting sites (such as the featured videos list on YouTube) being promoted on an external social bookmarking site (e.g. if slashdotted) or ranking high on a Google search. UGC objects in this class have to be popular according to the indexing algorithm used.

The second possible means of propagation is by word-of-mouth, sharing explicitly with a group of friends. This can happen through online social networks, emails, or out-of-band (face-to-face) conversations. This kind of viral propagation has been termed a social cascade and is considered to be an important reason for UGC information dissemination. The links between friends on an online social network explicitly capture the means of propagation for social cascades. Furthermore, many social networking sites include approximate geography information. Thus, information about the friends of previous users and their geographical affiliations could be used to predict the geographical access patterns of future users.

When users access a UGC object influenced by their friends, it can be modelled as if infected by the friends’ opinions. We envision that many ideas, messages, and products could be spread rapidly through our population as social epidemics. A recent example is the use of the hashtag \uksnow" on Twitter messages sent across the UK on Feb 2, 2009. Although there was no prior agreement on using this string, it quickly spread amongst Twitter users, and became the most popular hashtag. At its height, between 3pm and 5pm, nearly 2000 Twitter posts used the tag, making it the most popular hashtag of the day.

We investigate how information can spread across geographies as an epidemic. We take an empirical approach, using friend lists from an online social network (i.e. Facebook) to emulate a social epidemic. We crawled two sub-networks from Stanford and Harvard Universities. For Harvard students, the first 35,000 Facebook profiles belong to past students who were the first users Approximately 20,000 users with 2.1 million links now exist. The mean degree is 63, and a maximum degree is 911. The users have 1,660 distinct affiliations, of which 1,181 could be mapped to geographic locations allover the globe. We select a single user as an initial infectious user and propagate the infection process to their friends. This process is repeated over n rounds, with infection spreading from the initial seed to nodes n hops away.

This study shows two possible geographic distributions of infected users. First, a rapidly shifting epidemic is observed, where the infected population and the regional spread of the users changes from the third round to the fifth round. Second, the infection can also proceed without much change in geographic locations but rapid epidemic rate. The history of past locations can trivially predict the future when the epidemic is localised.
65: Marcus Kaiser, Claus Hilgetag and Arjen van Ooyen. No guidance needed: development of realistic spatial neural networks through competition and random growth    (abstract only)   information
Abstract. Neural connectivity at the cellular and mesoscopic level appears very specific, and is presumed to arise from highly specific developmental mechanisms. However, there are general shared features of connectivity in systems as different as the networks formed by individual neurons in Caenorhabditis elegans or in rat visual cortex and the mesoscopic circuitry of cortical areas in the mouse, macaque and human brain. In all these systems, connection length distributions have very similar shapes, with an initial large peak and a long flat tail representing the admixture of long-distance connections to mostly short-distance connections. Furthermore, not all potentially possible synapses are formed, and only a fraction of axons (called filling fraction) establish synapses with spatially neighbouring neurons. We found that random axonal growth away from the soma can already reproduce the known distance distribtion of connections. We also observed that experimentally observed filling fractions can be generated by competition for available space at the target neurons. These findings may serve as a baseline model for the spatial development of neural networks but may also be applicable to the formation of social and transpotation networks.
66: Yukio Hayashi. Robust and efficient design of geographical networks according to a population density    (abstract only)   information
Abstract. Many real networks, e.g. airline or railway networks, the Internet, and electric power grids, are embedded in a metric space, the efficient design principle may be involved with both topological and geographical measures such as the distance between nodes, the throughput of links, and the spatially distributed requests for the communication and the transportation. Based on several optimal policies related to these measures, geographical network models has been studied [1][2][3]. On the other hand, we have proposed an evolutionary construction of geographical networks [4] based on iterative divisions of an equilateral triangle (or square) according to the population density in a statistical data, and shown the good properties of the small modality of degrees suitable for the robust connectivity [5], bounded short distance paths, the planarity without crossing links, and an efficient routing with only local information [6]. Moreover, as similar to a branching process, the stochastic subdivision process makes an infinite state Markov chain, whose element represents the number of triangle (or square) faces on the layer defined in decreasing order of the size at a time step. We also derive the moving wave of the size distribution in a continuous approximation. On the same positions of nodes in our proposed geographical networks, we consider an extension of BA(Barabasi-Albert) model [1] in which typical network structures such as a nearest-neighbor graph, a scale-free network, and a star graph emerge within the preferential attachments w.r.t the degrees, the population, and the distance between the selected node and a new node at each generation step. We show that the send/receive requests proportional to the population density affects the spatial concentration of traffic flow measured by the betweenness centralities of links and nodes in comparison with the geographical and the BA-like networks.

[1] Y.-B. Xie et al., PRE 75, 036106, 2007.
[2] B. Xulvi-Brunet, and I.M. Sokolov, PRE 75, 046117, 2007.
[3] M.T. Gastner, and M.E.J. Newman, PRE 74, 06117, 2006.
[4] Y. Hayashi, Physica A 388, 991, 2009.
[5] T. Tanizawa, G. Paul, S. Havlin, and H.E. Stanley, PRE 74, 016125, 2006.
[6] P. Bose, and P. Morin, Theo. Comp. Sci. 324, 273, 2004.

Note: I would like to prefer the contribition talk.
67: Rae Zimmerman. Applying Network Theory to Urban Infrastructure    (abstract only)   information
Abstract. Network analysis is potentially highly applicable to many problems associated with infrastructures and their social importance, though network theory and applications are not well developed in this area. Two particular problems that lend themselves to network analysis are infrastructure security and sustainability currently at the forefront of public agendas internationally. One aspect of this is the growing concentration of infrastructure spatially and functionally, highlighting the need to decentralize infrastructure for security and environmental purposes while still maintaining concentrated settlement patterns to avoid sprawl development patterns.

This contribution presents research on a method for quantifying infrastructure networks based on node-link configurations, density and path counts in transportation, energy, water, and information infrastructures primarily for urban areas and the regions that support urban area infrastructure. Applications are presented based on publicly available data. In transportation, for example, ratios of the number of access points or stations (nodes) and number and length of track for rail transit reflect the extent of system coverage, flexibility, and degree of access. Similarly for highways, entrances and exits per mile and number and length of track give a comparable picture. Water and electric power production and distribution systems can be characterized according to points of convergence often not apparent without a study of the networks. Combining infrastructure network information with socioeconomic data for network users enables equity issues to be addressed. These computations can be made at the scale of regions, cities, neighborhoods and any other subarea.
FIELD: Information Networks and Infrastructures
68: Dashun Wang, Cesar Hidalgo, James Bagrow and Albert-Laszlo Barabasi. Social Mobility, of the Network Kind    (abstract only)   information
Abstract. For a contributed talk

Recent studies have described the temporal evolution and stability of collective social groups and ties in social networks, while leaving open questions about the dynamics of the relative positions that individuals occupy in the network. Generating a social network from a large dataset of cellular telecommunications, we concentrate on (i) explaining the role of repeated interactions in the stability of the position of individuals in the network; (ii) identifying which positions in the network are most stable and why; and (iii) quantifying the extent of social mobility (changes in friendship over time) observed in the data.  We show that analyzing the individual stability provides a quantitative understanding of social structures.
69: Stefan Wieland, Ana Nunes, Tomás Aquino and Andrea Parisi. Equilibrium topologies of adaptive contact networks with SIS dynamics    (abstract only)   information
Abstract. POSTER:
The spreading of diseases with the possibility of reinfection, covered by SIS dynamics, can be modelled on adaptive contact networks, where susceptibles try to evade infection by changing their contact patterns depending on the disease status of their neighbours. This interplay of disease dynamics and network alteration adds new phases to the standard SIS model (Blasius et al. 2006, Gross & Kevrekidis 2008) and, in the endemic phase, lets network topology settle down to a characteristic state. This final endemic state does not depend on the initial network topology, but rather on the two essential system parameters. We investigate those final topologies for each relevant phase of the system.
71: Mariko Hanabusa and Takashi Iba. Analysis on Collaboration Data of Voice Actors in Anime    (abstract only)   information
Abstract. (Abstract for Poster)

In this presentation, we show the result of our analysis on the collaboration data of voice actors in anime. Although voice actors have been getting to be popular as the animation industry grew in Japan, there are few studies about the relations among voice actors. We analyze the data of 820 series of anime which were broadcasted on television from December 1990 to November 2000 in Japan. In our study, three approaches are taken to understand the collaboration of voice actors in anime: (1) analyzing the collaboration graph of voice actors, (2) analyzing the structure of the collaboration graph chronologically, and (3) classifying works of anime based on the collaboration of voice actors. The collaboration graph consists of nodes which are voice actors, joined by links which are placed between voice actors who have co-acted in the same series of anime. The weight of a link depends on the number of the anime series on which they have acted together. The collaboration graph of whole 11 years from 1990 through 2000 consists of 2180 nodes and 81125 links, and it has a very short average path length: 2.435 and a high clustering coefficient: 0.73. Therefore it can be considered as a small-world network. We will also show the result of the chronological analysis with the collaboration graphs of respective years from 1990 to 2000.
72: Matteo Cavaliere, Attila Csikász-Nagy, Tarcisio Fedrizzi and Ferenc Jordán. Games generating networks    (abstract only)   information
Abstract. While our comparative knowledge is rapidly growing on static networks, it is increasingly important to much better understand network dynamics. We present a generative model for a complex network where adjacent nodes play the Prisoners Dilemma game and their obtained payoff, combined with graph grammar rules, determine iterative node-based replacements (rewriting) in the network. The initial network contains only cooperator (C) nodes, defectors (D) try to invade only at a certain point. We study (1) the effect of the defectors’ temptation on topology, (2) the effect of graph grammar rules on the outcome of the game and topology and (3) their combined effect. We are interested in (1) whether and how Cs can build a network that is resistant against future invasion of Ds, (2) how the “success” of Cs and Ds depends on the game and on the grammar rules and (3) what are the ways to achieve successful invasion. We compare our results to real longitudinal social network data and discuss their relevance also in an ecological context.
73: Xianglilan Zhang. NOT PROVIDED    (abstract only)   information
Abstract. In spite of many complex networks, whose degree distributions are found to obey power laws, have some similar attributes, their evolutionary mechanism, node behavior and its role during network formation remain fewly explored. While recent studies consider the formation of a scale-free topology largely to be attributed to a directed and selective process, called preferential attachment, we develop an alternative model using the core concepts in the theory of Games on Graph, its main feature being that networks are usually formed as a result of complex interactions involving many factors without any explicit directions. Specifically, we implement a repeated game-based framework incorporating five representative evolutionary rules. The network formed show many features of real social ones, such as a power-law degree distribution, hierarchical clustering and cooperative behavior. We suggest that both Cooperation and Competition appear to be required for the formation of a scale-free network. Moreover, it is node behavior rather than its original fitness decides final fitness and network structure. We conclude that Cooperation should also be considered as a necessary driving force when modeling the complex formation of any scale-free networks.
74: Eocman Lee, Jeho Lee, Jiwhan Lee and Dan Braha. Emergent Properties of Learning Dynamics on Hierarchical Networks    submission   information
Abstract. It is commonly known that bosses in an organization can lead subordinates in learning because the former have more experience and organization-related knowledge. What would happen if bosses do not have such experience or knowledge? Would there be no systematic difference in learning between them? We argue that even without prior experience or knowledge, bosses can do better. We show that this remarkable order in learning dynamics arises from the topological regularity inherent in a typical hierarchical structure.
75: francesca odella. Dimensions of Confidentiality in Group Communication: a Network Perspective.    submission   information
Abstract. The paper discuss and present the results of a network study performed among adolescents in high schools; the study of the networks of communication among the students was designed to evaluate the impact of new forms of communication (text and internet messaging) on their perception of privacy and confidentiality. The main assumption of the study is that privacy perception is related to group norms and not only to individual attitudes; confidentiality of communications is also gender sensitive and is influenced by educational standards such as the type of school.
The issue of privacy in network studies, has been debated more directly and extensively in theoretical papers (Strahilewits, 2001; Kadushin, 2005) which gave directions about ethical concerns and some hints on research practices. Attention in literature has been paid to the nature of information (secrecy, rumors and gossip) as a prominent factor for the structuring of information flow (conspiracy networks) and its degradation process (Di Fonzo and Bordia, 2006). Most of the analysis concentrated on the factors of influence on the information dissemination dynamics and elements such as the structure of the network (number of super-connected nodes, of weak and strong ties etc.), the technological constrains that contrast the diffusion of a piece of information and the cultural variables that facilitate the spread of it. Empirical studies, however, concentrated more on the analysis of group with special characteristics of confidence and secrecy, than on normal communications (Steglich and al., 2004): the disclosure of confidential and intimate information was also related to issues such as power and economic dominance (Kadushin and Alba, 1976; Baker and Faulkner, 1993).
The present study focused on the normal flow of communication among adolescents in prospective of ordinary events, such as invitation to a party, class assessments, expressions of individual sympathy and peer group cohesion. To highlight dimensions of confidentiality in group communication the analysis implemented relational dimensions of privacy, associated to specific structural properties of the networks (scale, density, connectedness) and evaluated their significance inside the specific social  and organizational environment (high schools).
Alba R. D. Kadushin C. (1976) The intersection of Social Circles: A new measure of Social Proximity in Networks, Sociological Methods and Research, vol.5., n.2, pp.77-102.
Baker, W.E., RR Faulkner, (1993) The Social Organization of Conspiracy: Illegal Networks in the Heavy Electrical Equipment Industry, American Sociological Review, vol.58, n.5, pp.837-860.
Borgatti S. P. and Molina J.L., (2005) ‘Towards ethical guidelines for network research in organizations’, Social Networks, vol.27,2, pp 107-117.
DiFonzo N. and P. Bordia, (2006), Rumor Psychology: Social and Organizational Approaches, American Psychological Association.
Kirke D. (2006), Gender and Chain Reactions in Teenagers’ Social Networks, Connections, vol. 27, n.1, pp.15-23.
Kostakos V., L. Little (2005), The social implications of emerging technologies, Interacting with computers, 17, pp.475-483.
Steglich, C., Snijders, T. and M. Pearson, ‘Dynamic Networks and Behaviour: Separating Selection from Influence’ (2004), ICS working paper, Groningen University.
Strahilevitz L. J. (2005), ‘A social network theory of Privacy’, American Law and Economics Association Annual Meetings, paper n.42, published online at The Berkeley Electronic Press.
76: Byungjoon Min, Kwang-Il Goh and In-Mook Kim. Waiting time dynamics of priority-queue networks    submission   information
Abstract. We study the dynamics of priority-queue networks, generalizations of the binary interacting priority queue model introduced by Oliveira and Vazquez [Physica A {\bf 388}, 187 (2009)]. We found that the original AND-type protocol for interacting tasks is not scalable for the queue networks with loops because the dynamics becomes frozen due to the priority conflicts. We then consider a scalable interaction protocol, an OR-type one, and examine the effects of the network topology and the number of queues on the waiting time distributions of the priority-queue networks, finding that they exhibit power-law tails in all cases considered, yet with model-dependent power-law exponents. We also show that the synchronicity in task executions, giving rise to priority conflicts in the priority-queue networks, is a relevant factor in the queue dynamics that can change the power-law exponent of the waiting time distribution.
(for a contributed talk)
77: Giovanni Petri, Henrik J. Jensen and John W. Polak. Congestion and information in traffic networks: dynamical percolation?    (abstract only)   information
Abstract. [This submission is for a contributed talk]

The interplay between information networks and transport networks is determining the flow on the latter. In particular congestion formation, persistence and elimination depend on how information is moved across the transport system. In line with a number of recent studies[1–3] , we model here these issues from a network theoretical perspective.
Our aim is to construct simple models which are able to produce qualitative as well as semi-quantitative insight into fundamental aspects of the dynamics of network congestion. We find that a global information distribution leads to significantly larger fluctuations in flow than when only local information is available.
Transport networks have indeed been object of many studies in recent years. In analogy to equilibrium fluid dynamics, steady-state descriptions[4] were proposed and studied in depth. Although they produce interesting results about local phenomena[5] they are not able to capture the inherent "intelligent" behaviour involved in route-planning and route-choosing. Micro-level agent-based models[6,7] solve the issue of individual choice, but require an enormous amount of detailed informations about the network (e.g. position and signaling of junctions, traffic lights synchronizing etc.).
We propose a minimal network flow model evolving under two sets of dynamical rules, representing different amounts of information each node has about the status of the system. One set considers each node as having complete information (global model), while the second considers each node as having only knowledge about its neighbourhood (local model). Nodes have a flow threshold over which they jam, stopping to receive incoming flow until their load decreases below their threshold. The outgoing flow of a node is depressed proportionally to the fraction of jammed neighbours in the local model and proportionally to the fraction of jammed nodes in the whole network in the global model. We monitor and characterize the arising jamming events as a function of the ratio between the load introduced in the network and the total network capacity, β , considering the size, time-dependence and topological structure of the evolving jammed subgraph.

Results from simulations show significant differences between low and high load regimes and between the two models, when this simple difference in the nodes’ information horizon, local or global, is embedded in the network. We see a stationary jammed population emerge under the "local information" dynamics for lower loads than under the "global information" dynamics. For higher loads we find that the system undergoes a non-trivial transition as the load on the network increases: as β increases from 0 to 1, the jammed subgraph grows through a discontinuous transition to half the network’s size (NJ
≃ N/2), but is unable to invade the whole network until β ≈ 1.05 − 1.1. The system then undergoes a second discontinuous transition to the completely jammed state NJ = N . Unexpectedly, we find that the fluctuations produced by the dynamics with complete information are very broadly distributed (with amplitudes up to 30% of the system’s size), while the ones produced under the local information dynamics are narrow and Gaussian-distributed, suggesting that for high regime the global information dynamics is more likely to produce wild and unpredictable oscillations and is thus less convenient for real traffic networks, where localized jams will be preferred to large, fluctuating jammed regions. Moreover, we observe that the survival time of jamming perturbations diverges for values of β much smaller than 1, signaling the presence of an endemic jammed population even for relatively small load regimes. This divergence coincides with the appearance of a connected component of jammed nodes in the networks, that grows through a pulsating invasive mechanism: the connected jammed component (core) jams its peripheral neighbours, which then relax on their unjammed neighbours, producing the oscillatory mechanism. The global dynamics exhibits larger oscillations because it effectively keeps the nodes nearer to their thresholds than the local, increasing nodes’ susceptibility to jamming. Thus peripheral neighbours’ relaxation induces jams in their previously unjammed neighbours, that will then relax themselves jamming again the core’s peripheral nodes and producing the large oscillating fluctuations. Also, this description sheds light on the nature of the two transitions, the first one being the appearance of the connected jammed component, the second the disappearance of the connected unjammed one.
In contrast to previous congestion studies[1,2] , the appearance of a discontinuous phase-transition[13] indicate that "susceptible" nodes, i.e. nodes nearer to their threshold than the average, might play an important role in the propagation and persistence of a jam. Indeed, this would suggest practical, though perhaps counter-intuitive, strategies to reduce the risk and persistence of jamming, as for example the selective closing of susceptible but not yet jammed stations in order to hinder the propagation of the jam. In order to better understand this behaviour, we build and study a simple dynamical percolation model that aims to mimick the flow model in order to compare its predictions with numerical experiments and test different strategies for congestion reduction.


1 - De Martino D. et al, Congestion phenomena on complex networks, Phys. Rev. E 79(015101), 2009;
2 - Scellato S. et al, Traffic optimization in transport networks based on local routing, arXiv:0901.1078v1 , 2009;
3 - Youn H. et al, Price of Anarchy in Transportation Networks: EfÞciency and Optimality Control, Phys. Rev. Lett. 101,
128701, 2008;
4 - Helbing D. , Gas-kinetic derivation of Navier-Stokes-like traffic equations, Phys. Rev. E, 53(3):253-282, 1996;
5 - Bando M. et al, Dynamical model of traffic congestion and numerical simulation, Phys. Rev. E, 51(2):1035, 1995;
6 - Dupuis A. and Chopard B., Cellular automata simulations of traffic: a model for the city of Geneva, Networks and Spatial Economics, 2002;
7 - Jacob R.R., Marathe M.V. and Nagel K., A computational study of routing algorithms for realistic transportation networks, ACM Journal of Experimental Algorithms, 4(1999es, Articlet No.6), 1999;
8 - Rosvall M. et al, Navigating Networks with Limited Information, Phys. Rev. E 71, 066111, 2005;
9 - M. Rosvall, K. Sneppen, Networks and Our Limited Information Horizon, arXiv:cond-mat/0604036v1, 2006;
10 - Dorogovtsev S.N. et al, Critical phenomena in complex networks, Reviews of Modern Physics, 80.1275, 2008;
11 - Newman N.E.J. , The Structure and Function of Complex Networks, SIAM Rev. Volume 45, Issue 2, pp. 167-256, 2003;
12 - Simonsen I., Helbing D. et al, Transient dynamics increasing network vulnerability to cascading failures, Phys. Rev. Lett. 100, 218701 (2008);
13 - H. Janssen et al. , Generalized epidemic process and tricritical dynamic percolation, Phys. Rev. E 70, 026114 (2004);
14 - A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendesm, k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects, Phys. Rev. E 73, 056101 (2006);
78: Alan Taylor, Desmond Higham, Ernesto Estrada and Jonathan Crofts. Mapping Directed Networks    (abstract only)   information
Abstract. Large complex networks may exhibit types of behaviour attributable to the presence of certain types of substructure. One such substructure is approximate bipartivity [2,3]. Here we have two subsets of nodes, S1 and S2, such that members of S1 have strong connections with members of S2, but S1 and S2 have weak internal connectivity. We consider specifically the case of directed networks, and wish to discover bipartite substructure that respects orientation, so that links point from S1 to S2, but not vice versa. We present a mapping that can be applied to a directed unweighted network. This mapping converts the unsymmetric adjacency matrix into a symmetric real valued matrix, with both positive and negative entries. We argue that large positive entries correspond to S1-S1 or S2-S2 pairs and large negative entries correspond to S1-S2 or S2-S1 pairs. Thus by reordering or clustering this new matrix, we can discover inherent directed bipartivity. The new mapping is motivated by the concept of an alternating walk, which successively respects then violates the directionality of the connections. Given an underlying directed bipartite structure, nodes belonging to the same set will be connected by a large number of alternating walks of even length. Likewise, nodes belonging to different sets will be connected by a large number of alternating walks of odd length. By considering the combinatorics of these alternating walks, we obtain a neat expression involving the singular value decomposition of the original adjacency matrix. We illustrate the advantages of this mapping over exponential-based measures of bipartivity using synthetic networks. We also apply the mapping to a c. elegans neural network, and show that biologically meaningful directed bipartite substructure discussed in [1] can be discovered from the connectivity information alone.

[1] R.M. DURBIN, Studies on the development and organisation of the nervous system of caenorhabditis elegans, PhD Thesis, University of Cambridge, 1987.
[2] E. ESTRADA, D.J. HIGHAM AND N. HATANO, Communicability and multipartite structures in complex networks at negative absolute temperatures, Physical Review E, 77 (2008), p. 026102.
[3] P. HOLME, F. LILJEROS, C.R. EDLING AND B.J. KIM, Network bipartivity, Phys. Rev. E, 68 (2003), p. 056107.
79: Hyun Keun Lee, Petter Holme, Fredrik Liljeros and Beom Jun Kim. An effective master equation for susceptible-infected-susceptible model    (abstract only)   information
Abstract. We propose an approximation to figure out the time evolution of nodes' infection probabilities in the susceptible-infected-susceptible (SIS) model in the network where the number of nodes is fixed while the links representing contact vary as time goes on. The master equation for the probability is simplified up to the second order of infection rate $p$ between the infected node and susceptible one, so that it provides an efficient way to estimate the time dependence of the infection probabilities of nodes for the small $p$. We also briefly survey the mean field equation for the SIS model in network, valid for not small $p$.
80: Ingo Scholtes. Breathing Life into Networks: Harnessing Complexity in Massive-Scale Networked Computing    (abstract only)   information
Abstract. Abstract for Contributed Talk:

The last decade of research in complex networks has delivered valuable insight into the emergent structure of natural, social and engineered systems. Among the intriguing results provided by this new branch of science is the fact that the remarkable performance and dependability of many of those systems emerge from simple local interactions between their constituents. Since massive-scale networked systems consist of inherently unreliable components, achieving comparable qualities is often hardly possible when using globally directed, deterministic network topologies. In contrast to this traditional paradigm, we argue for a novel approach to the engineering of such systems. It mimics the way how reliable macroscopic structures in nature emerge despite the intrinsic uncertainties at microscopic level. Building on recent findings from network science, we argue for large-scale networked systems that favor complex statistical structures and probabilistic qualities over pseudo-deterministic guarantees. The decentralized monitoring and adaptation of macroscopic properties provides interesting opportunities for adaptive and resilient systems. Apart from discussing the prospects of such a paradigm shift, we point out challenges lying ahead on the road to a world in which scalable and dependable computing systems grow and survive rather than being constructed and maintained.

These claims will be underpinned with actual techniques that have been developed for the domain of Peer-to-Peer networks. This class of distributed systems tries to achieve scalability and dependability not by relying on centrally managed infrastructures but rather by utilizing logical overlay networks built on top of user machines. We outline how the fact that this connectivity is alterable and widely independent from geographic limitations allows for systems that actively use phase transition phenomena occuring in complex networks. We further demonstrate how backscatter effects occuring in the synchronization of complex oscillator networks can be used to infer knowledge about a network's global emergent characteristics in a decentralized way.
81: Xin Lu, Linus Bengtsson, Tom Britton, Martin Camitz, Beom Jun Kim, Anna Thorson and Fredrik Liljeros. Evaluating efficiency of Respondent-driven sampling on a gay men web community    submission   information
Abstract. Respondent Driven Sampling (RDS) is a recently introduced, network-based sampling method for hidden populations that are generally difficult to access with standard probability sampling methods because of the lack of a well defined sampling frame. There has been a rapid increase in RDS research during recent years, with more than 120 empirical studies in 30 countries targeting a wide range of hidden populations, such as injection drug users, men who have sex with men, sex workers and their sexual partners. However, the estimators for RDS are based on several assumptions that may not be valid in real life. Particularly, the networks are assumed to be bipartite, respondents to recruit peers randomly and the sampling procedure to be with replacement. As the population is generally not known, biases introduce with these assumption are hard to determine. Existing theoretical and empirical studies have used mainly random network models or networks that do not constitute hidden populations. To evaluate the efficacy and efficiency of RDS on real networks, for the first time, we have used the largest Nordic web community for gay men. We have simulated the RDS on the network for testing the effect of violations against the basic assumptions behind RDS such as non-reciprocal structure and non-random edge selection.
82: Matthew Vernon and Matt Keeling. Individual and network models of infectious diseases of cattle    (abstract only)   information
Abstract. [This abstract submitted for consideration as a contributed talk]

The availability of comprehensive data on the movement of cattle in
the United Kingdom is both a challenge and a great opportunity for
epidemiological modelling. Contact network-based approaches have been
valuable in understanding the role of animal movements in the
transmission of infectious diseases. Typically, movements of cattle
are represented as a directed network, wherein animal holdings
are nodes, and movements of cattle are edges.

The network of cattle movements is one of the most detailed dynamic
network data sets available, and we discuss in this paper the
advantages and disadvantages of a range of representations of these
data for the purposes of epidemiological modelling. We demonstrate,
using stochastic disease simulations, that more complex, fully dynamic
network representations need to be deployed rather than the more
popular static network representations to fully capture the impact of
animal movements upon disease dynamics.

Additionally, we go further, and simulate the spread of disease at the
level of individual animals, rather than farms. With around 9 million
cattle alive at any one time in the UK, individual-based models are
computationally challenging, requiring substantially more resources
than farm-based network models. We consider what individual-based
models can tell us that farm-based network models cannot, and discuss
how they may refine network models of the UK cattle herd.

The comparison of farm-based network models and individual-level
models is challenging, as the former do not account for the disease
status of individuals, and the latter do not neatly describe the
disease status of holdings. We describe a new approach to this
problem, whereby mean final epidemic sizes (in terms of number of
farms that ever have infected cattle upon them) across a range of
parameter space for short-lived epidemics are established, and then
the distributions of final epidemic sizes and durations of epidemics
are compared between individual-based and farm-based models which
resulted in identical mean final epidemic sizes. We demonstrate that
this approach enables the outputs from the two different models to be
compared, and show how network-based models may be refined in the
light of findings from individual-based ones.
83: Jin S. Kim, Byungnam Kahng and Doochul Kim. Power laws and network representation of the seismic records in Sichuan    (abstract only)   information
Abstract. The statistics of seismic record are known to show scale-free nature. The Gutenberg-Richter distribution describes that the frequency of earthquakes with respect to their magnitudes in a seismic region follows a power law. The Omori's law implies that the interevent time distribution between two sequential earthquakes is given by a power law. It has also been pointed out that the spatial distribution of earthquakes' epicenter is fractal-like, thus there is a power-law relation between the length scale and area scale of earthquakes. We study these statistical properties for the Sichuan earthquake, occured during May to August, 2008 in Sichuan province of China. We compare the 2008's earthquakes to the previous ones in the same seismic region in the view point of such scale-free statistics. We also construct a network describing the spatio-temporal correlations among the earthquakes. The relation between power-law distributions in the seismic record and the structure of the earthquake network is discussed.

* Submission for a poster
84: Sandra Silva and Isabel Mota. Social Network Analysis in Economics: a bibliometric exercise    (abstract only)   information
Abstract. Since the end of the 1970s, it is clear the research broadening within economic theory, for example by showing a greater concern with social interactions (Manski 2000). For this reason, the systematization of the main elements of economic thinking on social interactions seems to be a relevant topic on economic theory research agenda.
In this context, our paper intends to offer an appraisal on a specific methodology for dealing with social interactions - the Social Network Analysis (SNA) – on economic research. We intend to categorize the contributions in this field by main research paths, using a bibliometric approach. The documentation exercise is based on a wide-ranging review of the abstracts from articles published in all economic journals over the past fifty years gathered from the Econlit database.
SNA has developed around a shared set of methods such as graphs, sociograms, and cliques, incorporating a high degree of formalization. It has been used in a wide range of scientific areas, from psychology and anthropology up to sociology and economics.
Preliminary analyses show Economic Sociology, Cultural Economics and Technological Change as the most important research areas that adopt the SNA perspective within economics. Based on our bibliometric study, we intend to corroborate the main research streams and, go deeper on the mapping of this scientific approach, by computing the key authors and top outlets. In broader terms, the results of this research will provide a framework for analyzing the evolution of SNA in economics and its potential future research directions.

Keywords: Social Network Analysis, Economic Methodology, Bibliometry
JEL-codes: B4, C89, D85, L14

Manski, C. F. (2000), “Economic Analysis of Social Interactions”, Journal of Economic Perspectives: 14(3): 115-136
85: Sergey Melnik and James Gleeson. Analytical results for bond percolation on clustered random networks    (abstract only)   information

An analytical approach to calculating bond percolation thresholds and sizes of giant connected components on random networks with non-zero clustering is presented. The networks are generated using a generalization of Trapman's [P. Trapman, Theor. Pop. Biol. 71, 160 (2007)] model of cliques embedded in tree-like random graphs. The resulting networks have arbitrary degree distributions and tunable degree-dependent clustering. The effect of clustering on the percolation thresholds is examined and contrasted with some recent results in the literature.
86: Filippo Radicchi, Santo Fortunato, Benjamin Markines and Alessandro Vespignani. Reputation diffusion and the ranking of scientists    (abstract only)   information
Abstract. Bibliometrics, the science analyzing citation data and the statistics derived from those,
ultimately focuses on ranking things $-$papers, authors, journals, disciplines$-$ assuming
that the rank is a quantitative measure of impact or popularity of the studied items. Recently,
the abundance of digital data enabled the implementation of graph based ranking
algorithms that provide system level analysis for ranking publications and authors.  
Here we take advantage of the entire Physical Review publication archive ($1893$-$2006$) to
construct authors' networks where weighted edges, as measured from opportunely normalized citation counts, define a proxy of the reputation transfer mechanism. On this network we define a ranking method
based on a diffusion algorithm that mimics the spreading of reputation credits on the network.
We compare the results obtained with our algorithm with those obtained by local point
such as the citation count and provide statistical analysis of the assignment of major career
awards in the area of Physics.
87: Pedro Rafael Costa, Marcio Luis Acencio and Ney Lemke. Network topology-based prediction of morbid and druggable genes    submission   information
Abstract. Introduction
The identification of both morbid genes, i.e. those genes involved in inherited human disease, and druggable genes, i.e. genes whose encoded proteins are targets for drugs, requires experimental approaches that are time-consuming and laborious. Thus, a computational approach that could accurately predict such genes would be invaluable for accelerating the pace of discovery of causal relationships between genes and diseases as well as the determination of druggability of gene products.
Computational approaches for predicting human morbid and druggable genes have been reported in literature and most of them have been shown to be reasonable predictors of gene morbidity (Perez- Iratxeta et al., 2002; Turner et al., 2003; Adie et al., 2005; Lopez-Bigas and Ouzounis, 2004; Jianzhen and Li, 2006) and druggability (Li and Lai, 2007; Han et al., 2007). However, as the availability of an integrated molecular network (IMN) of human genes comprising protein physical, metabolic and
transcriptional regulation interactions might provide us with new opportunity for discovering morbid and druggable genes by considering the topological features of this IMN, we propose here a novel machine-learning-based approach that relies on multiple topological features of an IMN of human genes to predict gene morbidity and druggability. We have previously and successfully applied this methodology to predict gene essentiality on Escherichia coli (Silva et al., 2008) and Saccharomyces
cerevisiae (Acencio and Lemke, in press).
To obtain the topological features used as learning attributes by the classifier algorithm, we first built a deterministic IMN of human genes by assembling databases of experimentally validated human genes interactions, namely BioGRID (Breitkreutz et al., 2008), Intact (Hermjakob et al., 2004) and DIP (Salwinski et al., 2004) for protein physical interactions, BIGG (Duarte et al., 2007) for metabolic interactions, and TRED (Zhao et al., 2005) for transcriptional regulation interactions. The resulting IMN is composed by 10,250 genes and 70,959 experimentally validated interactions. For the generation of the decision tree, the following network topological features obtained from the constructed IMN were used as learning attributes for each gene: clustering coefficient, closeness centrality and betweenness and degree centralities for each type of interaction (protein physical, metabolic and transcriptional regulation). After training the classifier on known human morbid or druggable genes, we assessed the performance of our classifier by holdout validation. This preliminary evaluation showed that, for prediction of morbid genes, the generated decision tree had a recall of 70%,
i.e. 70% of disease genes were correctly classified as such. For prediction of druggable genes, the generated decision tree had a recall of 72%, i.e. 72% of druggable genes were correctly classified as such.
By considering several topological properties of the constructed human IMN as learning attributes for training the selected classifier, the generated decision tree was able to correctly classify 70% of morbid genes of the training set, a performance comparable to other machine-learning approaches for morbid
gene prediction in which the recall ranged from 63% to 74% (Adie et al., 2005; Lopez-Bigas and Ouzounis, 2004; Jianzhen and Li, 2006). Regarding the prediction of druggable genes, our classifier was able to correctly classify 72% of these genes in the training set, a performance that is intermediate among those of other machine-learning approaches for druggable gene prediction (recall ranging from
60% [Han et al., 2007] to 80% [Li and Lai, 2007]).
We wish to thank FAPESP (research grants 2007/02827-9 and 2007/01213-7) for supporting this work.
B. J. Breitkreutz, C. Stark, T. Reguly, L. Boucher, A. Breitkreutz, M. Livstone, R. Oughtred et al. (2008): The BioGRID Interaction Database: 2008 update. Nucleic Acids Res. 36, D637-640.
C. Perez-Iratxeta, P. Bork and M. A. Andrade. (2002): Association of genes to genetically inherited diseases using data mining. Nat Genet., 31, 316–319.
E. A. Adie, R. R. Adams, K. L. Evans, D. J. Porteous and B. S. Pickard. (2005): Speeding disease gene discovery by sequence based candidate prioritization. BMC Bioinformatics, 6, 55.
F. S. Turner, D. R. Clutterbuck and C. A. Semple. (2003): POCUS: mining genomic sequence annotation to predict disease genes. Genome Biol., 4, R75.
F. Zhao, Z. Xuan, L. Liu and M. Q. Zhang. (2005): TRED: A Transcriptional Regulatory Element Database and a platform for in silico gene regulation studies. Nucleic Acids Res. 33, D103–D107.
H. Hermjakob, L. Montecchi-Palazzi, C. Lewington, S. Mudali, S. Kerrien, S. Orchard et al. (2004): IntAct: an open source molecular interaction database. Nucleic Acids Res. 32, D452-455.
J. P. M. Silva, M. L. Acencio, J. C. M. Mombach, R. Vieira, J. C. Silva, M. Sinigaglia, and N. Lemke (2008): In silico network topology-based prediction of gene essentiality. Physica A. 387, 1049-1055.
L. Salwinski, C. S. Miller, A. J. Smith, F. K. Pettit, J. U. Bowie, D. Eisenberg. (2004): The Database of Interacting Proteins: 2004 update. Nucleic Acids Res. 32, D449-451.
L. Y. Han, C. J. Zheng, B. Xie, J. Jia, X. H. Ma, F. Zhu et al. (2007): Support vector machines approach for predicting druggable proteins: recent progress in its exploration and investigation of its usefulness. Drug Discov Today. 12, 304-313.
M. L. Acencio and N. Lemke. (2009): Integration of network topology, cellular localization and biological process information predicts essential genes in Saccharomyces cerevisiae BMC Bioinformatics. In press.
N. C. Duarte, S. A. Becker, N. Jamshidi et al. (2007): Global reconstruction of the human metabolic network based on genomic and bibliomic data. Proc Natl Acad Sci U S A. 104, 1777-1782.
N. López-Bigas and C. A. Ouzounis (2004): Genome-wide identification of genes likely to be involved in human genetic disease. Nucleic Acids Res. 32, 3108–3114.
Q. Li and L. Lai (2007): Prediction of potential drug targets based on simple sequence properties. BMC Bioinformatics. 8, 353.
X. Jianzhen and Y. Li (2006): Discovering disease-genes by topological features in human proteinprotein interaction network. Bioinformatics. 22, 2800-2805.
88: Pietro De Lellis, Mario di Bernardo and Francesco Garofalo. Consensus and Synchronization of Complex Networks: theory and applications    (abstract only)   information
Abstract. In this talk we will discuss the problems of consensus and synchronization of complex networks of dynamical agents. After stating the problem, we will discuss novel adaptive strategies for to solve these problems. The idea is to use adaptive control strategies to evolve the coupling gains between agents in the network. Mutually coupled agents will exchange information and adapts the strength of their coupling in order to achieve a common asymptotic evolution. The role of network evolution will also be considered together with the problem of assessing robustness of the desired common trajectory in the presence of disturbances and topological variations. The theoretical derivation will be complemented by simulations on a set of representative examples.
89: Francesco Iorio, Roberta Bosotti, Antonella Isacchi, Emanuela Scacheri and Diego di Bernardo. DRUG NETWORKS: A network approach to study drugs and their mode of action    (abstract only)   information

Identifying molecular pathways targeted by a compound (drug mode of action - MOA) is a key challenge in biomedicine and of paramount importance for the development of new and powerful drugs. Prediction of drug MOA has been attempted in the past by using phenotypic features or, more recently, by comparing side effect similarities [Campillos et Al. Science 2008, Yeh et Al. Nat Genet 2009]. Attempts to use the transcriptional response of a cell to the compound in order to predict its targeted pathways, have so far met with limited success [di Bernardo et Al. Nat Biotech 2005].
Our aim was to build a “drug network” starting from a public reference dataset containing transcriptional responses of cells (in the form of genome-wide gene expression profiles – GEPs) following treatments with more than a thousand different compounds (1309 compunds for a total of 6100 GEPs). In this network, drugs sharing a subset of molecular targets should be connected by an edge or lie in the same community.
At the heart of our approach is a novel definition of distance between two compounds. This is computed by combining GEPs obtained with the same compound, but at different dosages or on different cell lines, via an original rank-aggregation method, followed by a gene set enrichment analysis [Subramanina et Al. Proc Natl Acad Sci USA, 2005] to compute similarity between pair of drugs.
The network is obtained by considering each compound as a node, and adding a weighted edge between two compounds if their similarity distance is below a given significance threshold. We show that, despite the complexity and the variety of the experimental conditions, our approach is indeed able to identify similarities in drug mode of action, where the neighbours of a drug are those with the same, or most similar, MOA. We validated the network by comparing our predicted similarities against repositories collecting information on compounds with known MOA (CHEMBANK and DRUGBANK). The first 100 strongest edges provided a PPV equal to 80%. Moreover, we observed that different communities in the network consist of drugs with different therapeutic applications (communities were computed using a heuristic version of the Girvan-Newman algorithm).
  We also validated our approach experimentally, by generating new expression data by treating three different cell lines with 16 compounds with known MOA, for a total of more than 100 microarrays. We added these compounds as new nodes in the network and we observed that 70% of them were correctly classified.
Our tool represents a unique approach to identify MOA of novel compounds using only transcriptional responses.
Abstract. (POSTER)
The understanding of a “community” of species living in particular ecosystem as a system of energy (or biomass), which flows from every population of autotrophic producers to a number of interconnected populations of consumers, is a quite basic idea for ecology. Such, so called, food or trophic networks play also an important role in many evolutionary explanations - from the level of adaptation, through speciation, to the level of macroevolution. Therefore, these networks are also very attractive objects for theoreticians, both analytics and modelers. In the last two decades many models dealing with the food networks were published. They were static or dynamic, also analytical or numerical, but most of them appeared rather complicated and they were based on less or more arbitrary, no intuitive assumptions.
I tried to go back to simplicity by designing a minimalistic individual based simulation, similar to predator prey lattice models, but stressing the role of energy, and allowing for practically unlimited number of agent species settling many different niches. Except the first one, each species in the model emerges by ‘‘atomic speciation’’ event, as a daughter agent of an agent belonging to one of the existing species. Then, depending on the local ecological interactions, such species survive, or extinct. The only criterion is the actual ability to obtain enough energy for covering all costs and an effective reproduction in the environment populated by other agents.
Almost like in natural ecosystems, a food network of the model is calculated indirectly from measured properties of individual interactions, but in opposite to real cases it could be complete, both in space and time, and susceptible to any imaginable experimental procedures.

For more details about the model see:
• Borkowski W., 2008. Cellular automata model of macroevolution. In Proceedings of the Fourteenth National Conference on Application of Mathematics in Biology and Medicine (pp. 18-25), Uniwersytet Warszawski, QPrint Warszawa 2008, ISBN:83-903893-4-7 (arXiv:0902.3919v1)
• Borkowski, W., 2009(?). Simple Lattice Model of Macroevolution. Planet. Space Sci. (pp. 12; accepted for publication in special issue), (doi:10.1016/j.pss.2008.10.001)
91: Karen Shoop and Raul Mondragon. One size fits all? Evaluating null models for academic networks.    (abstract only)   information
Abstract. Selecting an appropriate null network is vital for analysing the characteristics of social networks. A major concern is that an investigation of seemingly similar social networks may require a null network for each of the networks under study; essentially there may be no equivalent of a physical law to describe expected interactions between academics. Furthermore, the assumptions that underlie the null network may not in themselves reflect the behaviour of social networks.

This research investigates an academic department, fragmented into its constituent research labs. A static picture of these labs reveals divergent network structures. Multiple techniques for generating null networks are examined to produce a best fit to the different structures, and assessed using Newman’s modularity function. The results demonstrate that randomization based on the conservation of the density of connections and rank-preferential attachment produces a more plausible description of an academic network.

submission for a contributed talk
92: Ken Suzuki. Proposing a New Currency System Using Network of Transactions    (abstract only)   information
Abstract. The value of currency system is based on the network of transactions. However, there exist few studies from the perspective of complex network.

In this study, I propose a new currency system, the Propagational Investment Currency SYstem(“PICSY”), in which values propagate through a transaction network. Transactions are expressed as edges of the network. The network of transactions in PICSY is expressed as a matrix, and an eigenvector of the matrix means contribution to the society.

In the PICSY framework, every transaction is an investment. If person A sells goods to person B, such transaction is an investment in kind from person A to person B. As a result, person A can obtain an investment return or loss from sales made by person B.

Goods and services invoke subsequent reactions through a supply chain. For example, consumable goods are not only a composite of innumerable goods, but also can be seen as intermediate goods for labor. From this perspective, no 'final' goods exist in the world. The effects of goods and services are embedded in the subsequent goods. Therefore, it follows that the value of goods is also embedded in the subsequent goods. In this way, we can readily observe a chain of value propagation through the supply chain.

This study introduces three PICSY models using matrix calculation. These models must conserve eigenvector by matrix conversions. This constraint guarantees stability of currency value.

The idea of virtual company increases the matrix size. However, eigenvalue of the matrix is invariant after virtual disbandment of the company. The existence of virtual companies in PICSY virtualizes organizations in the real world.

Through this study, I demonstrate that PICSY increases fairness. There exists few rent in PICSY because every transaction is an investment.  Given this nature, PICSY can also be applied to personnel evaluation in a company.  I introduce a case study of personnel evaluation conducted by a 30-member weblog service company in Japan.

Applying this case study to a broader scope, in the end, PICSY is regarded as a world-wide personnel evaluation system using currency.

This work is for contributed talk.
93: Michael Gabbay. Mapping and Modeling Insurgent Network Structure and Evolution    (abstract only)   information
Abstract. I present a methodology for mapping insurgent network structure based on their public rhetoric. Cooperative links between insurgent groups are measured by the number of joint policy communiqués or joint operations claims. In addition, a targeting policy measure is constructed on the basis of insurgent targeting claims. Network diagrams which integrate these measures of insurgent cooperation and ideology are generated for different periods of the Iraqi insurgency and demonstrate meaningful changes which track the evolution of the strategic nature of the insurgency. Correlations between targeting policy and network structure indicate that insurgent targeting claims are aimed at establishing a group identity among the spectrum of rank-and-file insurgency supporters. A dynamical systems model is presented which evolves the relationship between insurgent group dyads as a function of their ideological differences and their current relationships. The ability of the model to qualitatively and quantitatively capture insurgent network dynamics observed in the data is discussed. It is shown that both ideology and pre-existing relationships are important determinants of insurgent group behaviors such as alliance formation.
94: Thomas Gorochowski. Dynamics of evolving complex networks    (abstract only)   information
Abstract. Networks in some form underpin virtually all complex systems making their study a fundamental tool for understanding system level behaviours. Much existing work considers such networks in a static context, neglecting the fact that in many real-world systems structure changes over time, evolving due to new requirements. Do rules exist governing this process and could they be used to efficiently evolve complex networks towards specific functions, or reliably control existing structures?

This talk will introduce possible methods for incorporating dynamic attributes into complex networks, with the aim of providing a coherent framework to investigate and model evolving structures. This will be based on networks of coupled ordinary differential equations where node and coupling dynamics can vary. We introduce the idea of a network "supervisor" whose task it is to re-wire the network such that a chosen performance measure is maximised. To illustrate some of these methods a simulation environment called NetEvo will be used to analyse how differing constraints and performance measures can effect the types of network produced. Finally, we outline the future directions of this work and the possible applications that may become possible.
95: Gerd Zschaler and Thilo Gross. "Rich stays rich" and full cooperation in the snowdrift game on an adaptive network    (abstract only)   information
Abstract. Contributed Talk

We study a model of cooperation based on the snowdrift game on an adaptive network, where both the evolution of strategies and the dynamics of the network topology depend on the individuals' fitness. The system evolves through two competing processes: players may adopt the strategy of more successful neighbors, or reshape their environment by cutting links to less fit individuals and rewiring to another randomly selected node. As in many (social) systems individuals' actions do not depend on local information only, we investigate the limiting cases of purely local (LFP) and global fitness perception (GFP) in our setup. With LFP, the pairwise comparison of accumulated payoffs of two neighboring individuals determines which of them is the fitter one, whereas with GFP, players compare the general performance of their strategies given by the average payoff taken over the whole population.

Employing individual-based simulations and analytical approximation through moment-closure techniques, we show that sufficiently strong payoff-dependence in the linking dynamics leads to interesting behavior in the stationary regime for both cases. As selective rewiring implies a ``rich-stays-rich'' mechanism for LFP, the creation of high-degree nodes is observed, and the network approaches asymptotically a star topology. In the GFP case oscillations appear in the fraction of cooperators at a critical rewiring rate. If rewiring is fast enough, the stable limit cycle collides with the boundary, and a homoclinic bifurcation leads to asymptotic full cooperation.
96: Anne-Ruxandra Carvunis, Matija Dreze, Mary Galli, Junshi Yazaki, Selma Waaijers, Viviana Romero, Matthew Poulin, Stanley Tam, Fana Gebreab, Dario Monachello, Amelie Dricot, Huaming Chen, Niroshan Ramashandran, Joshua LaBaer, Tong Hao, Claire Lurin, Michael Cusick, David Hill, Marc Vidal, Joseph Ecker and Pascal Braun. Mapping plant interactome networks    (abstract only)   information
Abstract. Abstract contributed for a talk.

Protein-protein interactions are an essential constituent of all cells and organisms. Proteome-scale protein-protein interaction maps, or “interactome maps”, have become an important source of information for biology. Interactome network maps contain countless hypotheses that can assist small-scale biological studies focused on one or a few proteins at-a-time. They also provide network information for topological analysis and help the development of large-scale dynamic models. Lastly, protein interaction information has been successfully combined with other types of large-scale data to further our understanding of pathways and biological networks.

Arabidopsis thaliana is one of the best-studied plant model organisms for which crucial genome-wide resources are available. Furthermore, the recent completion of sequencing projects for several plant genomes has revealed an enormous amount of conservation among their genomes. The Center for Cancer Systems Biology (CCSB - Boston) and the Salk Institute Genomic Analysis Laboratory (SIGnAL - San Diego) have started a collaboration to systematically map plant interactome networks by exploiting this high level of conservation. Making use of a genome-scale Arabidopsis thaliana protein-coding open reading frame collection (ORFeome) containing 14,000 ORF reagents generated by SIGnAL, we are employing high throughput, high-quality yeast-2-hybrid and protein array technology to create a first generation plant interactome map. This effort will be complemented by mapping experiments for selected rice (Oryza sativa) gene-products.

CCSB has developed a high throughput, robust platform for binary protein-protein interaction mapping and has published first draft maps for binary interactomes of H. sapiens and C. elegans and a second generation map of S. cerevisiae (Rual et al., Nature 2005; Walhout et al., Science 2000; Li et al., Science 2004, Yu et al., Science 2008). Importantly, we have implemented quality control mechanisms that can provide high confidence, validated binary interaction data for any interactome mapping project (Venkatesan et al., Nature Methods 2009; Simonis et al., Nature Methods 2009; Braun et al., Nature Methods 2009; Cusick et al., Nature Methods 2009).

Here we will present a first network analysis of the completely mapped ‘Space-1’ of the Arabidopsis thaliana interactome and a comparative analysis with previously mapped protein networks of yeast, worm and human.
97: James Bagrow. Non-traditional network visualization methods    (abstract only)   information
Abstract. Complex networks are characterized by a variety of statistics, such as the degree distribution and clustering coefficient.  To gain further intuition, researchers often draw pictures of networks, typically using circles and lines to represent nodes and links, respectively.  Much work has gone into advanced layout algorithms for these pictures, yet many networks are simply too big or too densely connected to be visualized with these "traditional" methods, and it can be difficult to compare networks drawn with different algorithms.  We present alternative methods to "draw" an underlying network which do not rely on these two- or three-dimensional drawings and their inherent limitations, illustrating new approaches to the problem of understanding network structure and dynamics.
98: Duygu Balcan, Vittoria Colizza, Bruno Goncalves, Hao Hu, Jose Ramasco and Alessandro Vespignani. Multiscale mobility networks and the large scale spreading of infectious diseases    (abstract only)   information
Abstract. **********************
Contributed Talk

The main questions yet to address in computational epidemic approaches aimed at realistic scenario analysis concern their reliability and how the latter is affected by the level of details integrated in the models.  In this context one of the most difficult feature to factor in is the multiscale nature of  human mobility networks. Here we consider a worldwide epidemic model including the traffic flow among all airports indexed by the International Aviation Transportation Association and study the effect of the introduction of small-scale commuting networks on the spatio temporal pattern  of the simulated epidemic. In order to obtain a reliable description of the commuting networks we analyze mobility data from 20 countries across the world and find a gravity model able to provide a global description of commuting patterns up to 300 kms. The key to this general representation is the definition of relatively homogeneous subpopulation regions obtained by a Voronoi decomposition centered around major transportation hubs.  Although the commuting flows are on average one order of magnitude larger than the airline flows we show that the large scale pattern of the simulated epidemics exhibit small variations with respect to the baseline case where only airline flows are considered.  On the other hand, the short range mobility does have an impact in increasing the synchronization of subpopulations in close proximity and in the epidemic behavior at the periphery of the airline transportation infrastructure. The present analysis opens the path to quantitative approximation schemes to calibrate the level of data resolution and the needed computational resources with respect to the accuracy in the description of the epidemics.

Contributed Talk
99: Hao Hu, Steven Myers, Vittoria Colizza and Alessandro Vespignani. WiFi Networks and Malware Epidemiology    (abstract only)   information
Abstract. ********************
* Contributed Talk *

In densely populated urban areas WiFi routers form a tightly interconnected proximity network that can be exploited as a substrate for the spreading of malware able to launch massive fraudulent attacks. We consider several scenarios for the deployment of malware that spreads over the wireless channel of major urban areas in the US. We develop an epidemiological model that takes into consideration prevalent security flaws on these routers. The spread of such a contagion is simulated on real-world data for georeferenced wireless routers. We uncover a major weakness of WiFi networks in that most of the simulated scenarios show tens of thousands of routers infected in as little as 2 weeks, with the majority of the infections occurring in the first 24–48 h. We indicate possible containment and prevention measures and provide computational estimates for the rate of encrypted routers that would stop the spreading of the epidemics by placing the system below the percolation threshold.

* Contributed Talk *
100: Bruno Goncalves, Marco Ajelli, Duygu Balcan, Vittoria Colizza, Hao Hu, Jose J. Ramasco, Stefano Merler and Alessandro Vespignani. Comparing large-scale computational approaches to epidemic modeling: Agent based versus structured metapopulation models.    (abstract only)   information
Abstract. ********************
* Contributed Talk *

Recent years have witnessed with increased frequency the use of computational models for the realistic simulations of epidemic spreading. Methodologies adapt to the scale of interest and range from very detailed agent-based models to large scale spatial metapopulation models. Worldwide modeling approach generally relies on metapopulation scheme where the long range mobility of individuals across subpopulation is accounted by airline traffic while the epidemic within subpopulations is modeled according to different coarse-grained stochastic or deterministic schemes. While these models are computationally scalable and allow the simulation of global epidemics in an efficient way, they do not possess the level of details offered by detailed agent based models used at the city or single country level. One major issue thus concerns to which extent the spreading pattern and epidemic impact found by different modeling approaches may differ and are affected by the different approximations and assumptions used to describe local population properties such as short time mobility, commuting patterns and population structure. Most important  

Methodology. We provide for the first time a side by side comparison of the results obtained with an agent based model and a metapopulation stochastic model for the evolution of baseline pandemic events in Italy. The metapopulation simulations use the global epidemic modeler (GEM) scheme that defines a stochastic epidemic model on the global scale that integrates airline travel flow data among all airports indexed by the International Aviation Transportation Association (IATA). The GEM uses high resolution census data and considers 3362 airports in 220 different countries and allows for the simulation of any arbitrary disease evolution structure worldwide (cite us). The model integrates commuting and age structure data for Italy. The agent based model is based on the explicit representation of all the individuals of the population considered. Highly detailed data (e.g., on the age structure of the population, on the household size and composition, on the employing rate by age) are employed for characterizing the set of the most important contacts for diseases transmission (i.e., household, school and workplace contacts). This kind of model allows the evaluation of the effectiveness of realistic, individually targeted, public health control measures. The models are synchronized in the initial conditions by using the same reproductive rates and defining the same imported infected and latent cases in Italy. This allows a one to one comparison at the granularity levels accessible in the two modeling schemes. We define the granularity levels at which the two model have both access. In particular we look at the spatio-temporal behavior of global quantities such as prevalence and morbidity. For both models the results are projected at the granularity level of Italian municipalities.  


The results obtained show that both models provide a consistent spatio-temporal pattern that is in very good agreement at the scales accessible in both approaches. The overall difference in the impact of the epidemic ranges from 8% to 11% depending on the R0 considered in the simulations. The metapopulation model consistently provides a larger prevalence with respect to the agent based model. This is an expected result inherent to the lack of details and structure in the intra-population contact pattern in the metapopulation model. The introduction of an age structured contact matrix further improves the agreement between the two models. The good agreement between the two modeling approaches it is very important in the definition of the tradeoff between computational costs, data availability and the information accessible by the models.  

* Contributed Talk *
101: Jean-Jacques Slotine. STRUCTURAL PRINCIPLES FOR DYNAMICAL NETWORKS    (abstract only)   information
Abstract. Most of the key results in network theory involve network architecture.
Comparatively much less attention has been devoted to {\it dynamics},
not just of the connections but of the nodes themselves. Clearly, only
so much can be deduced from architecture, and at some point, one has
to wonder what the nodes actually {\it do}.

The purpose of this talk is to show that systematic symplifying
principles, similar in goal to the known architectural principles, can
be derived in the context of dynamics; and also, that dynamic
considerations on networks impose architectural principles of their
own.  In particular, we study architecture from a global dynamic
functionality point of view, and discuss for instance why biological
evolution is likely to favor certain types of aggregate stability.

For illustration, although neurons as computational elements are 7
orders of magnitude slower than their artificial counterparts, the
primate brain grossly outperforms robotic algorithms in all but the
most structured tasks. An explanation involves both architectural
questions and specific dynamic questions.  The parallelism of brain
computations has extremely limited explanatory power, and much recent
functional modelling of the central nervous system focuses on (i) its
modular, heavily feedback-based computational architecture, the result
of accumulation of subsystems throughout evolution and (ii) the
specific distributed computational power of using spiking neuronal

Oral presentation
102: Dario Ghersi and Maurizio Filippone. An efficiency analysis of the U.S. airport network    submission   information

Transportation systems play an essential role in our society and have been the subject of extensive study in a variety of disciplines.  Airport networks, in particular, have been analyzed both from a topological and dynamical point of view, with studies ranging from the degree distribution of the network to the spread of  epidemics.

In this work, we tracked the evolution of the U.S. airport network from 1988 to 2008 by mining a public database and constructing per-day networks of U.S. airports defined by the available flights. More specifically, we focused our analysis on the efficiency of the network considered on a daily basis from a geographical and temporal perspective, the latter achieved by treating the airports as nodes embedded in the non metric space of actual flight time. The global and local efficiencies measures proposed by Latora et al have been normalized by the cost of the network, to account for the fact that adding more links between airports leads to an increase of the overall maintaining cost of the system.

The analysis of the scores throughout the years reveals weekly and seasonal trends, as well as important historical events, such as the dramatic loss of efficiency following September 11th, 2001.
Interestingly, the picture provided by the temporal analysis is different from the purely geographical one, indicating an appreciable reduction in the network efficiency when looked from the time perspective, despite almost constant values of efficiency when defined in the geographical space.
103: Sergey Dorogovtsev, Jose Mendes, Alexander Samukhin and Alexander Zyuzin. Organization and function of modular networks    (abstract only)   information
Abstract. We discuss the global organization of heterogeneous equilibrium networks
consisting of well distinguished interconnected modules. We show how to
obtain the statistics of connected components and an intervertex
distance distribution in these modular networks, and to quantitatively
describe their architectures. Furthermore, we consider the evolution of the intervertex distance distribution with an increasing number of interlinks connecting
uncorrelated modules. We demonstrate that even a relatively small number
of connections between modules unite them into a network with mutually
equidistant vertices. Finally, we describe various processes taking place
in these complex networks, their specific Laplacian and other spectra, and
synchronization phenomena.

For a contributed talk (S. N. Dorogovtsev)

Network theory: methods, models, visualizations
104: Sang-Woo Kim and Jae Dong Noh. Non-equilibrium phase transition in network model    (abstract only)   information
Abstract. Dynamic systems have been studied widely on fixed networks. But most of real networks are not fixed. Moreover, dynamic systems may influence the structure of underlying networks. In order to understand the structure of such evolving networks, we investigate a weighted network model. Our model consist of $N$ nodes, $L$ edges, and $M=\rho N$ particles. Each link is assigned to a weight $w$. Each particle is randomly hopping to a neighboring node increasing weights of all edges attached to a target node. Then each edge is rewired with the probability $1/w$, or its weight decreases to $w(1-d)$. The model reduces to the one studied in Ref. [1] when $d=0$. It shows that the coupled dynamics of particles and edges leads to and instability toward formation of a hub with a dynamics transition. When $\rho$ is small, a hub appears spontaneously due to statistical fluctuations. On the other hand, a hub appears as a result of competition among smaller degree nodes when $\rho$ is large. When $d /= 0$, the model displays a new interesting feature. We find that there is a stationary state phase transition. To a given value of $\rho$, the network has a random network structure when $d>{d}_{c}(\rho)$. On the other hand, when ${d} < {d}_{c}(\rho)$, the network evolves into a state with multiple hubs. The number of hubs is proportional to ${N}^{0.326}$, and the degree of hubs is proportions to ${N}^{0.695}$. Performing extensive numerical simulation, we obtain the phase diagram between the states with and without hubs. We also present an effective theory explaining the mechanism of the phase transition.

[1] Sang-Woo Kim and Jae Dong Noh, Phys. Rev. Lett. 100, 118702 (MAR 2008)

105: Christian Thiemann, Daniel Grady and Dirk Brockmann. Tour de Sys: The Traveler's View of a Network    (abstract only)   information
Abstract. The plight of the Flatlander is imperfect information about a high-dimensional object. Yet even so, the clever inhabitant of a low-dimensional world can gain a great deal of information about such an object by examining it from many perspectives. We analyze complex transportation networks by using shortest-path trees to measure universal network properties from different locations. Furthermore, by defining a measure of a node's geographical access area we give a more realistic characterization of the centrality or remoteness of a location. The network topology indicates a clear distinction between the center and edge of a network, but we find that examining the weights of links is crucial, as the distinction in the weighted network for some quantities is even more pronounced. Often prior research has not focused on the weightedness of transportation networks, in spite of the fact that this property has an obvious bearing on how the networks are actually used. We show that measuring networks with weighted edges significantly affects their statistics. Our analysis indicates dynamical processes occurring on these networks should behave in a manner very different than what is predicted by considering topology alone.
106: Rafael Brune, Christian Thiemann and Dirk Brockmann. Universality and the Lack of it in Multiscale Human Mobility Networks    (abstract only)   information
Abstract. Although significant research effort is currently devoted to the understanding of complex human mobility and transportation networks, their statistical features are still poorly understood. Specifically, to what extent geographical scales impose structure on these networks is largely unknown. In particular, in light of the use of human mobility models in the development of quantitative theories for spatial disease dynamics, a comprehensive understanding of their structure is of fundamental importance. The large majority of statistical properties (degree distributions, centrality measures, clustering, etc.) of these networks have been obtained either for large scale networks or on small scale systems, indicating significant yet poorly understood deviations. We will present the first investigation of multiscale and multi-national mobility networks, covering length scales of a few to a few thousand kilometers. We will report that certain properties such as mobility flux distribution are universal and independent of length scale, whereas others vary systematically with scale. In particular, controversial properties such as scale-free degree distributions lose their heavy tails in small to intermediate length-scale windows.
107: Kwang-Il Goh. Network thinking in human disease and medicine    (abstract only)   information
Abstract. In this Invited Talk, I will review recent results on the application of network thinking to human disease and medicine. First I will motivate why we need network thinking in disease. Then a couple of specific examples of disease-related networks such as the human disease network and the drug-target network will be introduced. Finally, I will discuss what we have learned and what is to be learned from this line of research.
108: Vera Pancaldi and Jürg Bähler. Prediction of fission yeast protein-protein interactions based on gene and protein information    (abstract only)   information
Abstract. Introduction: Although large-scale experiments are elucidating more and more details of the interactomes of many species, the task of uncovering the wiring of genetic and protein interaction networks will require a huge experimental effort as well as strict data quality assessment protocols. As a complementary approach, we can use the information already available about genes and proteins to predict the most probable links in these complex networks. The fission yeast, S. pombe, is our organism of choice, as it complements the distantly related budding yeast, S. cerevisiae, to gain insight into universal biological processes. For both these yeast species a vast amount of genome-wide expression data has been collected under different environmental and genetic perturbations, complementing the information available in databases.

Method: We train a Support Vector Machine (SVM) to classify pairs of proteins into interacting and non-interacting. The positive training set is a list of high-quality, experimentally verified budding yeast protein-protein interactions, while the negative set is constructed as a complementary list of random pairs of budding yeast proteins. The features of the SVM belong to the following categories: physical parameters (position on chromosome, length of ORF, etc), protein information (mass, isoelectric point, amino acid composition, Nitrogen and Sulphur content, etc), Gene Ontology annotation (GO-SLIM), and experimental data (mRNA length, Pol II occupancy, correlation of expression under various conditions, time-correlation in many time-course experiments ). All features are collected for both yeasts, so that the budding yeast data are used to train the SVM, whereas the fission yeast data are used to predict new fission yeast interactions. The time-correlation of expression over many time-courses is estimated using a robust Bayesian two sample test approach [1]

Results: The performance of the prediction method is verified by cross-validation, where an accuracy of >80% is obtained. Moreover, some of the new predictions are set into the biological context of the specific pathway to which they belong and are currently in the process of being experimentally verified.

[1] O. Stegle et al. (2009), A robust Bayesian two-sample test for detecting intervals of differential gene expression in microarray time series, Lecture Notes in Computer Science (RECOMB), to appear.
To be presented as a talk or poster.
109: Petra E Vertes and Tom Duke. The Effect of Network Topology on Pattern Recognition in Neural Networks    (abstract only)   information
Abstract. SUBMISSION FOR: talk and/or poster

Despite a wealth of knowledge at the micro- and macroscopic scales in neuroscience, the way information is encoded at the mesoscopic level of networks of a few thousand neurons is still not understood. Polychronization is a newly proposed [1] mechanism of neuronal encoding which attempts to bridge this gap and which has been suggested to underlie a wide range of cognitive phenomena, from associative memory to attention. This encoding is based on millisecond-precision spatiotemporal firing patterns, corresponding to so-called polychronous groups, that have been shown to emerge spontaneously in simple, biologically plausible models of neural networks.

Here, we investigate the effect of network topology on the ease and reliability with which input stimuli can be distinguished by such a network, based on their encoding in the form of polychronous groups. We find that, while scale-free networks are unreliable in their performance, small-world and modular architectures perform an order of magnitude better than random networks at such discrimination tasks in a variety of situations. Furthermore, we find that these topologies introduce biologically realistic constraints on the optimal input stimuli for the system, performing best with inputs consistent with the topographic organization known to exist in many cortical areas. Finally, we investigate the capacity of such networks to distinguish between signals involving overlapping sets of input neurons and suggest that, for optimal performance, the network should be locally as well as globally small-world but should only show large-scale modularity.

These topological constraints on both networks and stimuli seem consistent with the first experimental findings on the cortical network architecture (see review [2]  and references therein) suggesting that these are optimal for information processing through polychronization.

We thank Eugene Izhikevich and Danielle Bassett for helpful advice and discussion.

1. Izhikevich E: Polychronization: computation with spikes. Neural Computation 2006, 18:245-282.
2. Bassett D, Bullmore E: Small-world brain networks. The Neuroscientist 2006, 12(6):512-523.
110: Carlo Gianelle and Giancarlo Ruffo. Discovering the network topology of labor mobility: structural determinants and directions for policy    (abstract only)   information
Abstract. Paper submitted for contributed talk.

The paper investigates the topology of the inter-firm labor mobility network in the leading Italian region of Veneto. Using a unique matched employer-employee dataset that covers the entire private sector population throughout the 90s, we construct a directed graph in which the vertices symbolize firms and the links represent transitions of workers between firms. The resulting network, roughly comprised of 380,000 vertices and 1,900,000 edges, is a scale-free small-world denoted by hierarchical clustering. The high degree of interconnection, the redundancy of paths, and the short distances all contribute to guarantee mutual accessibility to most labor market locations.
We argue that the observed clusterization is, at least partly, the result of the interplay between the geographical and sectoral dimensions embedded in the data, reflecting a peculiar feature of the Veneto economy: the phenomenon of industrial districts, i. e. firms located in proximity to one another, whose productive activities are tightly interwoven along the value chain, and whose competitive advantage relies on the widespread presence of specific skills in the local labor market.
The negative relation between the number of connections and the level of clustering appears to be governed by two different regimes: relatively flat for firms up to 50 employees, much steeper for larger firms. The switching region almost coincides with the transition from small to more structured organizations. In particular, the medium-size firms (50-250 employees), which represent the by far most dynamic component of the Veneto economy, emerge distinctively as the actors able to span the labor market beyond the boundaries of the district or the local cluster.
At the top level of the structure, the firms with the highest connectivity can be classified into three main categories: long-tradition manufacturing companies; chains of department stores, supermarkets, and companies performing services directly at the costumer’s place; temporary employment agencies. The last category represents a great novelty in the Italian labor market, since private agencies for employment services were allowed to operate by law only in 1997, and in just three years they have come to hold a prominent role within the network architecture. On the contrary, the large manufacturing firms, which have been the protagonists of the regional economy over the last decades, now, under the increasing competitive pressure stemming from emerging countries, appear to be the weakest nodes of the entire system. We believe such hubs should deserve special attention from the public authority, since their failure would lead to an unprecedented situation whose consequences cannot be fully predicted.
On the whole, our study allows to qualify precisely some phenomena which are well-known in the economic literature, but whose definition has always relied upon anecdotal evidence, case studies, or macro-level investigations. We also find a variety of quantitative results that are at least compatible with some major economic process undergoing during the period we study. Finally, we locate the key players upon which the very character of the network depends, and in so doing we provide the policy makers with useful and ready-to-use indications about the potentially most risky elements in terms of global accessibility of the labor market.
111: Christian Darabos, Ferdinando Di Cunto, Marco Tomassini, Paolo Provero and Mario Giacobini. Generalized Boolean Networks with Topology Driven Dynamics    submission   information
Abstract. *** See attached PDF version for better formatting ***

*** Field: Networks in Biology

Nowadays, it has been widely accepted that genes are the central pillar of biological evolution, and therefore of life as we know it. When considered as a static element of information, genes are relatively well know, with the fast advances achieved in numerous projects on identifying and sequencing tens of thousands of human genes, amongst other organisms. On the contrary, very little is known about genes as part of a dynamical biological system. Highly complex regulating interactions take place amongst genes to permit the evolution of the organism overtime. These interactions can be represented a genetic regulatory networks (GRNs), showing the influence of a gene on the others. Sadly, interactions in GRNs are very subtle and intricate, and ill understood, and for the parts of these GRNs we know, the confidence in the data drops as the size grows. Nevertheless, GRNs are the next big thing, and are the center of tremendous research efforts from the biological community. The quantity and quality of results in the field, thanks to modern high-throughput molecular genetics methods, such as microarray technology, that make real-life data available like never before, are bound to follow the same exponential trend as the gene sequencing did in its time. In the mean time, however, it is possible, and useful, to abstract many details of the particular kinetic equations in the cell and focus on the system-level
properties of the whole network dynamics. This Complex Systems Biology approach, although not strictly applicable to any given particular case, still provide interesting general insight.

Random Boolean Networks (RBNs) have been introduced by S. Kauffman more than thirty years ago [4] as a highly simplified model of GRNs. Each node represents the state Si of gene and each directed edge, the influence of a gene on another. Nodes also have a distinct function attached that decides state changes according to the state of the genes that have an incoming edge. The state S of the system is defined as the ensemble of all the nodes states Si . As they are fully deterministic, these systems, when starting from an arbitrary state S at time t = 0, will go through a set of transient states before eventually cycling in a subset of states called an attractor. RBNs have been studied in detail by analysis and by computer simulations of statistical ensembles of networks, and they have been shown to be capable of surprising dynamical behavior. Kauffman’s RBN model rests on a few main assumptions:
1. the fact that the nodes implement Boolean functions and their state is either on or off. ;
2. the Boolean function deciding of the gene’s next state are determined at random and potentially different within each node;
3. the interaction edges are drawn at random, according to a normal distribution;
4. the system is fully synchronous and uses discrete time-steps.
Considering current knowledge about GRNs, some of Kauffman’s assumptions are now subject to criticism. In our research, we aspire to inject modern knowledge into the original RBN model, making it more realistic.

Network topology: According to present data many biological networks, including GRNs,seem to be of the scale-free type output degree distribution, where the probability of a node to have an output degree k follows a power law p(k) = 1
Z k−γ . In 2003, M. Aldana [1] presented a detailed analysis of a model Boolean network with scale-free topology for RBNs. In our model, we have adopted this new topology. Even more recently, small parts of real-life GRNs have been discovered in which data were sufficiently reliable to specify actual interaction, with different
confidence rate though. We have have used the core transcriptional network in embryonic cells published by Chen et al. [2] and a portion of the yeast cell-cycle by Stoll et al. [5] as substrate for our RBN model.

Timing of events: Early on, the strictly synchronous timing of events has been questioned. Rather, genes seem to be expressed in different parts of the network at different times, according to a strict sequence. Therefore, we conclude that neither fully synchronous nor completely random asynchronous network dynamics are suitable models. In our opinion, the activation sequence in a RBN should be in some way related to the topology of the network. Therefore, we considered the influence of one node on another as active biological enhancing or repressing factors: only when the state of the node is turned or stays on has this node an effect on the
nodes downstream in the cascade. On the contrary, nodes changing their state to or remaining off have no impact on nodes they have outgoing links to, thus breaking the cascade. We have called this update scheme the Activated Cascade Update (ACU) [3].

Random Boolean functions: Today, we believe the the Boolean function is closer to an additive function, where the influence of the genes upstream the concerned one, along with its own current activity state, could be summed in a way that takes into account the enhancing or repressing effect of each influencing node [5].

We analyze in details the dynamical behavior of statistical ensembles of networks in terms of attractor number and length, and resilience to a common type of failure, that is the transient flip of a gene to the reverse state. Results are encouraging, as our model shows comparable and usually better performance and resilience to perturbations than the original.

Acknowledgements: M. Tomassini and Ch. Darabos gratefully acknowledge financial support by the Swiss National Science Foundation under contract 200021-107419/1. M. Giacobini acknowledge funding (60% grant) by the Ministero dell’Universit´a e della Ricerca Scientifica e Tecnologica.

[1] M. Aldana. Boolean dynamics of networks with scale-free topology. Physica D, 185:45–66, 2003.
[2] Xi Chen, Han Xu, Ping Yuan, Fang Fang, Mikael Huss, Vinsensius B. Vega, Eleanor Wong, Yuriy L. Orlov, Weiwei Zhang, Jianming Jiang, Yuin-Han Loh, Hock Chuan Yeo, Zhen Xuan Yeo, Vipin Narang, Kunde Ramamoorthy Govindara jan, Bernard Leong, Atif Shahab, Yijun Ruan, Guillaume Bourque, Wing-Kin Sung, Neil D. Clarke, Chia-Lin Wei, and Huck-Hui Ng. Integration of external signaling pathways with the core transcriptional network in embryonic stem cells. Cel l, 133(6):1106–1117, 06 2008.
[3] Ch. Darabos, M. Giacobini, and M. Tomassini. Semi-synchronous activation in scale-free boolean networks. In F. Almeida e Costa et al., editor, Advances in Artificial Life, 9th European Conference, ECAL2007, volume 4648 of Lecture Notes in Artificial Intel ligence, pages 976–985, Heidelberg, 2007. Springer-Verlag.
[4] S. A. Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol., 22:437–467, 1969.
[5] Gautier Stoll, Jacques Rougemont, and Felix Naef. Representing perturbed dynamics in biological network models. Physical Review Letter E, 76, 2007.
112: Marco Frassoni, Maurizio Napolitano and Davide Setti. Taolin, the open source Enterprise 2.0 web desktop    (abstract only)   information
Abstract. (Poster)

Taolin is an open source Web desktop created in the research institute Fondazione Bruno Kessler (FBK). The main goal of Taolin is to let researchers share and coordinate their efforts strengthening collaboration and improving working life.

The web desktop consists of a personal dashboard customisable by adding micro-applications called widgets. Each widget offers a different service that can be provided as a view over internal services or repositories (e.g. access to papers repository) or as a communication service (e.g. jabber web chat) or as an external resource (e.g. Google search).

Taolin social feature is exposed in a region reserved for user profile. A user can updated her profile using text, pictures and other contact information as well as office position (pinned on a map) and scientific publications. Information are associated to tags, creating a folksonomy and binding users together with the content. Activities performed by the users are reported in a shared timeline, and can be replicated by other users with one single click, so that increased visibility can cause cascade behaviour and a sense of community.

From a technological point of view Taolin relies on a 3-tier architecture: the back-end has been developed using CakePHP (a Model-View-Controller framework) over a PostgreSQL database (chosen for its stability and reliability), while the front-end takes advantage of the usage of JavaScript and AJAX (the framework adopted for the development is ExtJS, integrated with jQuery). JSON (JavaScript Object Notation, a lightweight data-interchange format) is used for the data transmission between back-end and front-end.

The Taolin platform is released as open source under the Affero GPL license. This means it can be reused, modified, studied and improvements made by other developers are going to be redistributed back to the community.
Given our goal of studying social networking and Web platforms impact on work life, our contribution with the creation of Taolin and its release as open source is in developing automatic tools for social network analysis as long as Web platforms. Hence we devoted special attention to the logging strategy in order to enable the subsequent analysis of social networks and system usage.

Further information, demonstrative screenshots and source code are available at Taolin website:
113: Ganna Rozhnova and Ana Nunes. Fluctuations and oscillations in a simple epidemic model    (abstract only)   information
Abstract. We show that the simplest stochastic epidemiological models with spatial correlations exhibit two types of oscillatory behaviour in the endemic phase. In a large parameter range, the oscillations are due to resonant amplification of stochastic fluctuations, a general mechanism first reported for predator-prey dynamics. In a narrow range of parameters that includes many infectious diseases which confer long lasting immunity the oscillations persist for infinite populations. This effect is apparent in simulations of the stochastic process in systems of variable size, and can be understood from the phase diagram of the deterministic pair approximation equations. The two mechanisms combined play a central role in explaining the ubiquity of oscillatory behaviour in real data and in simulation results of epidemic and other related models.

The submission is for a contributed talk.
114: Danica Vukadinovic Greetham, Abhijit Sengupta and Juliette Richetin. Simulating Social Networks Influences on Physical Activity Behaviour    (abstract only)   information
Abstract. (Contributed poster)

We want to model external social network influence on individual physical activity behaviour. In this work, behaviour is measured as a number of hours of exercising per week. Each individual is represented by an agent and social network between them is given in advance and it does not change during the simulation.
We start with the simple model where each agent has a continuous variable representing behaviour, and is trying to improve difference between ideal and actual self doing some amount of physical activity. The social network effect is introduced using a model of dual threshold, where an individual is “persuaded” to do the activity if the percentage of his neighbours doing it is higher than the first threshold, and if percentage is lower than the second threshold, he/she is persuaded to abstain from physical activity.  We than introduce another variable called “attitude” to each agent, which represents his positive/negative attitude toward behaviour and look at the effects of social networks to attitude and behaviour separately.
We implemented both models in NetLogo and ran the simulations with different distributions of thresholds and values for individual actual and ideal selves. We compared results using different theoretical and empirical models of underlying social networks.
115: Muhittin Mungan and Jose J. Ramasco. Who is keeping you in that community?    (abstract only)   information
Abstract. ********************
* Contributed Talk *

The components of complex systems are often classified according to the way they interact with each other. In graph theory such groups are known as clusters or communities and different techniques have been proposed to detect them. Recently, a Bayesian inference method for finding clusters based on connection similarity was introduced. We show that a stability analysis is able to measure the extent to which each element influences its neighbours' group membership. This allows us to identify the key elements responsible for the groups and for its resilience to changes in the network that we will call stabilizers. The output of the statistical inference is the most likely partition to have generated a graph like the one given, the identification of the stabilizers is thus of great relevance since without them such partition would not be statistically viable. Our approach provides a ranking of the nodes according to the amount of information they pass to their neighbours on group membership. Such identification conveys useful insight into real-word networks, where the grouping is typically related to functional units within the system as we will show with several practical examples obtained from different disciplines: social systems, food-webs and semantic networks.

* Contributed Talk *
116: Michela Ferron, Paolo Massa and Francesca Odella. Supporting Collaborative Networks in Organizational Settings using an Enterprise 2.0 platform    (abstract only)   information
Abstract. Coordination and networking among people working in the same organization is not a trivial activity. Collaborative web platforms, sometimes termed Enterprise2.0, have a great potential of improving effectiveness inside the work environment.
In this paper we report the ongoing creation of an open source Enterprise2.0 platform and its deployment inside Fondazione Bruno Kessler (FBK) research institute.
The goal of the Web platform, named Taolin, is to improve collaboration and knowledge sharing between FBK researchers and employees, with an emphasis on the social networking aspect. Technically it is a mashup of different services offered through customizable widgets.
The Taolin platform became operational in April 2008 and the deployment itself followed a network strategy. Indeed we are opening the system to colleagues incrementally: only users enabled by us, we call them champions, are able to actively use the Web platform and this means the nodes of the networks increase with time. The network strategy consists in the fact users already in the system can suggest colleagues who are not in the system yet. In this way we are able to increment our user base in a controlled way and to steer our development according to suggestions and feedbacks. In fact the Web platform is "always in beta" and we invite champions to have a proactive role by suggesting new features and basically being involved in the development loop. At March 2009, there are currently 90 champions out of around 400 employees.

We are currently planning to analyze different social network patterns emerging from the platform usage which can be mined from the stored logs.
In particular, we are going to analyze the network of chat contacts and comparing it with a more static network of relationships (an example of a static network could be the formal organization chart, or a sociometric network). There are other networks we intend to study. Users can view colleagues profiles and these visualization patterns can be represented as an additional network. The interface features a timeline displaying recent activity such as other users adding a widget; a champion can replicate the same action on her own interface. The collection of such logs can originate a network which is based on who added a new widget following whom and represents patterns of cascading adoption of technological tools. Moreover, users can suggest other colleagues as new champions and this information as well can be aggregated as a social network.
An important aspect of our analysis is the temporal dimension, since the nodes of the networks themselves are increasing in time so that it is possible to study the evolution of the social networks and their changes.
By releasing the Taolin Web platform as open source, we would like to be able to replicate the same analysis in more organizations, possibly in larger ones.

Type of submission: contributed talk.
117: Vittoria Colizza, Tore Opsahl, Pietro Panzarasa and Jose J. Ramasco. Prominence and control: The weighted rich-club effect    (abstract only)   information
Abstract. **********************
Contributed Talk

Uncovering the mechanisms that underpin the patterns and strength of
interactions among the elements of networked systems helps enhance our
understanding of the global organization, functioning, and performance of
these systems. In the rich-club perspective, emphasis is placed on a select
subset of nodes, namely the members of the club, with a view to detecting
interaction patterns and hidden orderings among them. Inspired by topological
rich-club measures that explore the tendency of highly connected nodes to
interact with one another, and drawing on results pointing to the fundamental
role played by the intensity and capacity of interactions in many network-related
processes, we introduce a new general framework that explicitly takes the
weights attached to ties into consideration, and enables us to investigate how
select nodes in a network distribute their efforts to one another. We propose
three different criteria for defining club membership, introduce the corresponding
appropriate null models, and apply the developed framework to three real-world
networks in the fields of transportation, scientific collaboration, and online
communication. We observe non-trivial weighted rich-club effects that shed a
new light on the management and distribution of traffic in transportation
networks, on how scientists allocate resources in collaborative endeavors, and
how online users direct their attention to one another.

Contributed Talk
118: Satoshi Itoh, Takaichi Ito, Kenji Kumasaka and Takashi Iba. Analyzing Collaboration Network of Editors in Japanese Wikipedia    (abstract only)   information
Abstract. (Abstract for Poster)

The purpose of this research is to clarify the creation process in mass collaboration. For the purpose, we analyzed how editors co-write articles in Japanese Wikipedia from 2002 to the end of June 2008, using several data logs of 75 “Featured Articles”.

In this research, we classified editors’ activities into two role types; “writer”, and “corrector”, and found that most of editors work as corrector. Furthermore, we visualized the interactions among editors as networks, and classified them into three types by numbers of editors, which mean scales of collaboration, and average characteristic path lengths, which mean the characteristics of interaction among editors. The networks also show us some characteristics of creation process in Japanese Wikipedia; amount of edit, roles and attitudes of each editor.

The results imply that Japanese Wikipedia has variety of editors’ roles in common and the diversity of interaction structure between editors.
119: vincenzo belcastro, Luisa Cutillo, Francesco Gregoretti, Gennaro Oliva and Diego di Bernardo. Untangling biological complexity: inference and analysis of a global network of gene-gene regulation in human cells.    (abstract only)   information
Abstract. Mammalian cells are extremely complex and their survival and proliferation is finely regulated by the interaction of tens of thousands molecules. The key challenge is to identify all of these molecules, the massive set of interactions among them and to understand their function.
Thanks to the advent of high-throughput techniques, it is now possible to measure gene expression levels of all the known genes in a mammalian cells under thousands of different conditions (i.e. drug treatment, gene knockdown, etc.). Such information can be interpreted using methods derived from quantitative sciences to learn the network of gene–gene inter-actions [Bansal, Belcastro et al, Molecular Systems Biology, 2007].
Here we developed a novel algorithm to infer gene-to-gene interactions and applied it, for the first time, to a massive collection of 20255 microarrays (HG-U133A) coming from 703 different experiments in a variety human tissues measuring 22283 human transcripts. For comparison up to now, the most recent to infer gene network in humans used less than 400 microarrays [Bass et al, Nature Genetics].
Transcripts are the nodes of the network; an edge between two nodes is weighted according to their strength of interaction, as measured by Mutual Information. Such gene network is a map of all direct and indirect regulatory interactions among genes. Genes involved in the same molecular pathways lie in the same communities in the recovered network. Here we show how this network is extremely useful in discovering gene function and in elucidating the molecular basis of genetic disease.
Our algorithm consists of a normalization step, via the application of a novel discretization procedure, that yields a single dataset containing comparable expression values, followed by the computation, for each pair of transcripts, of their Mutual Information (MI), which weights their statistical dependence.  MI was computed for over 200 million transcript pairs in human. Due to the computational time required, we designed, implemented and tested an efficient parallel version of the algorithm.
Validation of the resulting network in human is non-trivial. We first compared our inferred interactions against four published protein-protein, metabolic and kinase-substrate interaction networks. 14691 probesets over 22283 of the human network have at least one interaction, for a total of 277945 interactions. The network has an exponential degree distribution. By sorting the recovered interactions according to their weights, we obtain a ROC curve that exceeds 90% of correct predictions; more than 60% of the 15.000 highest scoring edges are correct; a random prediction would have inferred not more than 11. We also checked whether we could assign functions to genes via a “guilty-by-association” technique, i.e. for each gene, its predicted function is the one that is most common among its neighbors. We show, on a training set, that we can correctly assign gene function more that 40% of the time. We also applied the [Wakita, Toshiyuki,, 2007] community finding algorithm to the human network and show that the more that 60% communities we obtained are enriched for gene with similar functions.
Here we show that massive expression datasets, including a variety of different tissues and cell types, if properly analyzed are able to shed light on gene regulation and gene function. Our human network can be a unique tool to help molecular biology and molecular medi-cine research.
120: Gerd Zschaler, Alejandro Mora and Thilo Gross. Dynamics of a SIRS epidemic model on an adaptive network    (abstract only)   information
Abstract. Adaptive evolution of the network topology depending on the local state of the nodes provides a more realistic approach to the propagation of diseases on social contact networks. We investigate the dynamics of a susceptible-infected-(recovered/removed)-susceptible (SIRS) epidemiological process on an adaptive network. Depending on the rate of destruction of links to nodes on the R state, this state can represent either (i) a recovered individual with wanning immunity, or (ii) a removed individual and susceptible population turnover. In addition, new links are permanently created and destroyed between susceptible and infected nodes. The system behavior is treated analytically by means of a system of ordinary differential equations that include pair correlations and a moment closure approximation. Their numerical solutions and corresponding adaptive network simulations show the emergence of epidemic thresholds and Hopf bifurcations to regimes with oscillations in the disease prevalence. Finally, applications to real epidemics are discussed.
121: Daniele De Martino. Congestion phenomena on complex networks    (abstract only)   information
Abstract. submission for a contributed talk

We study a minimal model of traffic flows in complex networks,
simple enough to get analytical results, but with a very rich
phenomenology, presenting second-order as well as first-order phase transitions
between a free-flow phase and a congested phase.
It consists of random walkers on a queuing network with one range repulsion
that can be destroyed only when they move.
We focus on the dependence on the topology as well as on the level of traffic control.
We are able  to obtain transition's curves and phase diagrams analytically for the
ensemble of uncorrelated networks and numerically for single instances.
We find that traffic control improves global performance, enlarging the free-flow region in parameter space only in heterogeneous networks
The model also reproduces the cross-over in the
scaling of traffic fluctuations empirically observed in the Internet,
explaining it in terms of the inherent queuing mechanism.
122: Eduardo Lopez. Limited path percolation pahse transition: How violently does a system get disconnected?    (abstract only)   information

A large number of networks, such as social networks or the Internet, are the medium in which transport takes place. Disruptions of parts of these networks due to congestion or breakdown are typical and have consequences on the overall transport of the network. Limited Path Percolation (LPP) is a new model that addresses this problem. But this model, which differs from usual percolation because it only accepts paths that do not exceed a given relative length increase after the failures, is not yet fully understood. Here, I address the question of how violent the communication breakdown is in the LPP model, ie, what is the order of the phase transition from connected to disconnected phases. By analysing the length increase of paths on a network when links are gradually degraded, I find that the transition from connected to disconnected occurs in a discontinuous way, corresponding to a first order phase transition. The main consequence of this is that systems in which LPP applies, a drastic communication breakdown occurs, and the system suddenly becomes useless. This behaviour is in contrast with regular percolation, where a continuous second order transition occurs. I discuss the relevance of these results to problems in communication and infectious disease prevention.
123: donal bisanzio, luigi bertolotti, alessandro mannelli, charlotte ragagli, giuseppina amore, laura tomassone, paolo provero and mario giacobini. On the modelling of epidemic spreading in vector-host systems    submission   information
Abstract. The emergence of zoonotic vector-borne diseases in the last decade has increased the importance of better understanding their dynamics. A key factor in these pathologies is the contact between the vectors and their hosts/reservoirs, which allows the transmission of the aetiological agents. As many other biological systems, also these complexes can be modelled and studied by the use of networks (Newman, 2002; Massad et al, 2008). The topology of the structure, and in particular its small-world or scale-free properties, may affect the dynamical behaviour of pathogens transmission. In fact, it has been proven that in scale-free networks the epidemic threshold of a compartmental model tends to zero when the population goes to infinite (Pastor-Satorras and Vespignani, 2001). This characteristic of epidemiological networks results in an orthogonal approach with respect to the classical basic reproductive number (Davis et al, 2008). Thus, in several epidemiological systems, that can be modelled by scale-free networks, the epidemic threshold becomes a better estimation of disease spreading.
An interesting example of vector-borne disease is the Lyme borreliosis, a zoonoses transmitted in Italy by Ixodes ricinus ticks. The agents, bacteria of genus Borrelia burgdorferi sensu lato, are transmitted between ticks and hosts (mainly small mammals, birds, reptiles) which can be reservoir for the pathogen. The distribution of ticks on their hosts shows an aggregate behaviour, that seems to follow a negative binomial law. We tested these observations on data collected in Tuscany, Italy. Preliminary fittings suggest that frequency distributions of ticks on mice and lizards are better described by power law equations, showing exponents between 1 and 2. For the characteristic of I. ricinus' life cycle, i.e. a complete blood meal on a single host per tick stage (larva, nymph, adult), the number of contacts with hosts may be modelled as a Poisson distribution. From these results and observations, we focused on the modelling of the structure of contact in Lyme disease using bipartite graphs. Bipartite graphs are networks with two families of nodes and where links can exist only between nodes of different families. The Lyme borreliosis system can be studied using this class of networks also because the probability of transmission of Lyme's agent between ticks by co-feeding (two ticks feeding nearby on the same host) can be considered negligible. Transovaric transmission from females to eggs occurs with very small probability (less than 1%), and, in a first abstraction level, can be omitted. The distribution of links can be different for every nodes' family. In particular, for a study on the epidemiological threshold on this network class, three combinations of degree distribution laws are relevant: random vs random (R-R), random vs scale-free (R-SF), scale-free vs scale-free (SF-SF). To investigate the behaviour of the epidemic threshold on these structures we used Susceptible-Infected-Susceptible (SIS) compartmental model. First, the dynamical behaviour of these networks was studied when probabilities of vector to reservoir and reservoir to vector transmissions are uniform, and when the vectors and reservoirs populations remain constant through time. The simulations showed that the epidemic threshold for R-R remains is constant when the size of population grows up, instead for SF-R and SF-SF decreases. These results confirm the theoretical results found by Gómez-Gardeñes and colleagues (2008). The second step was building a network closer to the Lyme's dynamics, better simulating the contact between immature stage and reservoirs. For this reason, we set a fixed degree of two for the ticks’ nodes, keeping the hosts’ degree distribution as power law with exponents in the range observed in the analysis of field data. Also for these networks, the epidemic threshold decreases when the population goes up. In epidemiological terms, the decrease of the epidemic threshold in SF-R means that, when in ticks and reservoirs increase in a territory, Lyme disease is more likely to become endemic.

Davis, S.; Trapman, P.; Leirs, H.; Begon, M. & Heesterbeek, J. A. P. (2008), 'The abundance threshold for plague as a critical percolation phenomenon.', Nature 454(7204), 634-637.

Gómez-Gardeñes, J.; Latora, V.; Moreno, Y. & Profumo, E. (2008), 'Spreading of sexually transmitted diseases in heterosexual populations.', Proc Natl Acad Sci U S A 105(5), 1399-1404.

Kiss, I. Z.; Green, D. M. & Kao, R. R. (2006), 'Infectious disease control using contact tracing in random and scale-free networks.', J R Soc Interface 3(6), 55-62.

Massad, E.; Ma, S.; Chen, M.; Struchiner, C.; Stollenwerk, N. & Aguiar, M. (2008), 'Scale-free network of a dengue epidemic', Applied Mathematics and Computation 195(2), 376-381.

Newman, M. E. J. (2002), 'Spread of epidemic disease on networks.', Phys Rev E Stat Nonlin Soft Matter Phys 66(1 Pt 2), 016128.

Pastor-Satorras, R. & Vespignani, A. (2001), 'Epidemic spreading in scale-free networks.', Phys Rev Lett 86(14), 3200-3203.
124: Alexander Samukhin, Sergey Dorogovtsev and Jose-Fernando Mendes. Spectral properties of uncorrelated random networks    (abstract only)   information
Abstract. A unified approach is presented, which allows to treat spectral properties of
local linear operators on a random graphs. Adjacency operator and Laplacian on
uncorrelated random graphs with arbitrary degree distribution are considered as
important exampes. Spectral problems are reduced to the solution of nonlinear integral equations, containing degree distribution as a functional parameter. Relations of the asymptotics of spectral densities at small and large eigenvalues with the properties of the degree distribution are found analytically. It appears, that the only large eigenvalue parts of the spectral densities of bothe operators are related with the large-degree tail of the degree distribution. At the same time, the most interesting feature of the spectra - its density at low eigenvalues - is related with the minimal degree of vertices in the random graph.
125: Vinko Zlatic. Hypergraph topological quantities for tagged systems    (abstract only)   information
Abstract. Recent years have witnessed the emergence of a new class of social networks, that require us to move beyond previously employed representations of complex graph structures. A notable example is that of the folksonomy,  an online process where users collaboratively employ tags to resources to impart structure to an otherwise undifferentiated database.  In a recent paper~\cite{Gourab09} we proposed a mathematical model that represents these structures as tripartite hypergraphs and defined basic  topological quantities of interest. In this paper we extend our model by defining additional quantities such as edge distributions, vertex similarity and correlations as well as clustering.  We then empirically measure these quantities on two real life folksonomies, the popular online photo sharing site Flickr and the bookmarking site CiteULike. We find that these systems share similar qualitative features with the majority of complex networks that have been previously studied. We propose that the quantities and methodology described here can be used as a standard tool in measuring the structure of tagged networks.
126: Michela Rancan. Social Networks in the Mutual Fund Industry    (abstract only)   information

  Interpersonal connections are an important source of information and people can exchange also very useful information. But in a competitive setting, like financial markets, sharing information is less trivial. In this paper we try to understand how a social network could be a relevant dimension even in a context where agents compete amongst each other. We focus on the mutual funds industry. Previous works consider the mutual fund industry as a marketplace where managers compete like in a tournament. Even though managers compete amongst each other this does not prevent funds managers from being "friends" to exchange useful information. We consider connections rooted in the past, namely the institutions attended from graduate and undergraduate studies. We use a unique dataset on American mutual funds from 1996 to 2007. We gather data from Morningstar Principa CD_roms and Internet to collect a complete dataset on managers educations. Data on mutual funds and funds holdings are respectively from CRSP and Thompson Financial Stock Holdings.
    We find that managers who attended the same academic institutions hold similar portfolios. This could be driven just by the fact that fund managers who attended the same university have a similar "forma mentis" and background, rather than being influenced by word of mouth. Therefore we perform the analysis to include quarterly changes in holdings.
    A manager is more likely to buy (sell) a particular stock in a given quarter if managers who belong to the same network, do that. If we consider indirect linkages among managers this effect is lower. This confirms the hypothesis that mutual funds managers, who were class-mates share information, but valuable information does not probably travel to far in the network. The last finding is consistent with the theoretical result in Stein (2008).
    Social networks is an important dimension in financial markets and even professional investors use informal communication as a source of information. Further research is needed to understand if social interactions among funds managers can emphasis behavioral biases in portfolio choices, like underdiversification and "local bias".
    Moreover, our novel dataset allows us to study hiring in this specific labor market. Focusing the analysis at the family fund level we compute the concentration index (developed by Ellison and Glaeser, 1997). Our results suggest that across years, fund families tend to hire managers from certain academic institutions. This concentration is stronger when we consider universities for graduate programs (particularly master of business administration). These results could be explained by geographic proximity, reputation or social interactions  Our next research step will be disentangle those effects.
    In conclusion our preliminary findings suggest that academic interactions rooted in the past are relevant in the mutual funds industry, both for the trading behavior and for the labour market.
127: Natali Gulbahce and Albert-Laszlo Barabasi. Viral Disease Networks    (abstract only)   information
Abstract. Contributed Talk
Protein-protein interactions are of central importance to almost all biological processes in the cell. Global-scale human protein-protein interaction network is becoming more complete due to high-throughput methods. Recently, virus-human protein-protein interaction networks are also becoming available. These interactions provide an invaluable insight into the disease mechanisms viruses induce and are the building blocks of our analysis on two widely studied viruses, Epstein-Barr virus B95-8 and Human Papillomavirus type 16. We show that by using protein-protein interactions, gene-disease associations, microarray and population medical history data, it is possible to modularize virus proteins and isolate disease causing proteins and the pathways they hijack. We also find that these viruses target specific regions of the human interactome and that certain genes regulated by virus-targeted transcriptional factors show significant expression change in nasopharyngeal carcinoma (EBV), Burkitt’s lymphoma (EBV), and head and neck squamous cell carcinoma (HPV-16). We also observe that the results of gene-disease relationships predicted by our viral disease networks also manifest themselves in the population.
128: Olga Pustylnikov and Kirill Medvedev. Information Flow in Morphological Derivation Networks    submission   information
Abstract. In this paper, we present an evaluation of different entropy measures on language networks. We introduce the notion of a morphological derivation network (MDN) which is defined as a multi-level graph (Mehler, 2008). The vertices of an MDN are of three different types: words (and word stems), suffixes and part of speech categories. Relations are established by means of derivation relations in a language, e.g. a derivation from sun" (noun) >  sunn-" >  y" > adjective is a possible path in an English MDN. The networks are induced from natural language texts by means of the morphological derivation game (MDG) (Pustylnikov, 2009). The MDG system was constructed to examine the morphological structure of any input language. The game integrates an algorithm to induce the best derivation suffixes by statistical decomposition of words.

We compare the entropic measures which are based on splitting the network into j-spheres, or regions where the shortest distance between vertices is equal j, as proposed by (Dehmer, 2009) to simpler entropy measures. The goal is, to examine the information flow in networks of languages of a different morphological complexity. In particular, we evaluate the entropy measures on English, German and a random language (constructed from an unstructured set of random vocabulary). The results support generalizations on the typological structure of the languages under consideration. That is, typologically distinct languages can be distinguished by their MDNs. The presented approach contributes to the clarification of the role of entropy in measuring of information in language networks.
129: Alejandro Mora, Jose Daniel Munoz and Harish Padmanabha. Epidemic dynamics on spatio-temporal networks: The Dengue fever host-vector bipartite network model    (abstract only)   information
Abstract. Dengue Fever is a human arboviral disease which is transmitted by the domestic mosquito Aedes aegypti and constitutes one of the most widespread tropical diseases around the globe. The only way dengue fever virus can spread is the transmission from human to human via the mosquito. This agent based model considers hosts (humans) and vectors (mosquitos) as nodes of a spatial bipartite network where the links represent the possible interactions between them. The local spreading of the virus between neighboring households is driven by moving mosquitos, while the human mobility accounts for the long distant propagation of the disease. The simulated spatio-temporal system reveals rich dynamical behavior with epidemic thresholds, classes of phase transitions, and synchronization properties. The model is extended to include disease control/immunization strategies and analyzed within the adaptive networks conceptual framework. Validation of the model with field epidemiological data is discussed.
130: Gautier Krings and Francesco Calabrese. Micro- and macro-networks: how do groups of nodes interact?    (abstract only)   information
Abstract. Abstract for contributed talk

In network science, group membership is typically determined by the characteristics of the network itself, without reference to external node or edge features. However, in many real networks it is clear that other factors – such as location, income, or topic – will influence the way that groups are created and maintained. We show that if the assignment of agents to a group is made randomly, then the derived edge intensity distribution of the grouped network (macro-network) can be computed simply by knowing the group size distribution and the average probability that two nodes are connected in the  network of individual interactions (micro-network). This provides a new way of testing whether a given macro-network has been created from a random grouping of nodes in the micro-network, or whether it is related to the structure of the micro-network.

As an application, we study the network of interactions between the 2.5 million customers of a mobile phone operator in Belgium. We show that the structure of the macro-network of inter-city communications is affected by the home address of the customers, suggesting that our social networks are significantly affected by the overall association of people to a city, state, or country. This has implications for network design and capacity planning, as well as for the analysis and simulation of large scale human networks.
131: Gautier Krings, Francesco Calabrese, Carlo Ratti and Vincent Blondel. Gravity model in inter-city communication network    (abstract only)   information
Abstract. Abstract for contributed talk

To date, researchers have been unable to predict the large-scale features of aggregate social networks. In this work, we analyze the anonymous communications patterns of 2.5 million customers of a Belgian mobile phone operator. Grouping customers together by billing address city, we obtain a two-layer network: the lower layer, which we term the microscopic network, is built from individual customers’ calling behaviors; the upper layer, which we call the macroscopic network, is built from 571 towns and cities in Belgium.
Using the mobile phone network, we are able to show that the macroscopic network has both a degree distribution and an edge weight distribution with lognormal characteristics. We find that inter-city communications can be characterized by a gravity model: the intensity of communication between two cities is proportional to the product of the two populations divided by the square of the distance between them. Furthermore, we observe that intra-urban communications scale superlinearly with city population. Finally, we demonstrate that the observed macro-network features are influenced by the geographical distribution of customers.
132: Vincent David and Dirk Brockmann. Spatial scale in human mobility networks - What can we learn from renormalization?    (abstract only)   information
Abstract. We investigate the statistical properties of multi-scale human mobility networks in response to sequential, spatial renormalization, i.e. merging nodes according to their geographic proximity as opposed to network topological adjacency [1]. As a proxy for a human mobility network we employ the network of flux (weighted links) of bank notes between counties (nodes) in the United States [2] quantified by a strongly heterogeneous, symmetric weight matrix. We report that the distributions of link weights and node strengths (cumulative weights per node) are invariant under renormalization whereas the degree distribution is not. A comparison to embedded homogeneous networks and gravity models for human mobility indicates that the observed features are unique to real, multi-scale human mobility networks. We hypothesize that the observed spatial renormalization invariants can be connected to the long term evolution of mobility networks, e.g. optimal service or minimal cost measures. Our results may also pave the way to account theoretically for broad distributions and their functional shape in transportation networks.

[1] Radicchi et al. Complex Networks Renormalization: Flows and Fixed Points. Phys. Rev. Lett. (2008) vol. 101 (14) pp. 4

[2] Brockmann et al. The scaling laws of human travel. Nature (2006) vol. 439 (7075) pp. 462-465
133: Hugues Bersini. Immunologists : The true pioneers of the « new »  science of complex networks    submission   information


In this talk, I would like to pay a tribute to some researchers specialized in theoretical immunology (Perelson, Coutinho, Varela, Stewart, Weishbuch, De Boer and many others …)  and who, more than 20 years ago, published a series of seminal works dedicated to the idiotypic network, one possible immune system proposed in the seventies by the Nobel Prize of Medicine, Niels Jerne. They did anticipate by their works the current vague of interest for complex networks. The idiotypic network is one kind of protein/protein network formed by the antibody proteins binding among themselves. In their work, beyond the impact of this network on keys immunological foundations such as the self/non-self distinction, they studied:
- The different possible topologies of idiotypic networks: random, homogeneous, heterogeneous, with hubs, clusters… In fact, they compiled some very first sort of experimental “microarray data” coming from antibodies, and were able to spot some very preliminary topological maps of this protein network (although with very few nodes). They then tried to reproduce this topology by some software simulations, where the concept of shape space was introduced (a node occupies a position in a very abstract multidimensional space and the affinity between two nodes depend on their distance in this space). The binding then is far from random and depend on the nature of the two nodes.
- The way these topologies result from the structural evolution of these networks (the network grows in size by a constant recruitment of new cells). Rather than the very unlikely preferential attachment (in biology at least), they propose the concept of metadynamics, where new nodes are randomly recruited but will stay in the network as long as they bind with the existing current nodes (i.e. as long as they keep being stimulated by them).
- The way the dynamics (the concentration of the nodes change in time) and the metadynamics (the structural evolution of the network by introduction and disappearance of nodes) interact to shape the topology and to alter the dynamics of the nodes. Through a very subtle intertwined loop, the new coming nodes are dependent on the current topology and the dynamics of the current nodes, while the new coming nodes modify both the topology and the dynamics of the current nodes.
- The way the functionalities of these networks highly depend on their topology and how their disfunctionning could result in serious diseases (like autoimmune diseases) to be attributed to these “topological perturbations”. They followed in time the concentration dynamics of some of the nodes and showed that patient presenting autoimmune symptoms could equally show a very different dynamical regime for some of these nodes.
- They did connect this kind of biological networks with other networks coming from very different fields such as computer networks or sociological networks.
- They also discussed at large why and how biology in general could be the scientific field gaining the most from this new (at their time) science of networks... Today focus of an important part of the researches in biology tend once again to confirm their predictions.

All these works have been published at the time in various journals like PNAS or Journal of  of Theoretical Biology and would, I think, deserve a special historical tribute such as the one done on behalf of Lord May in the last year Netsci.
134: Romualdo Pastor-Satorras and Andrea Baronchelli. Effects of mobility on ordering dynamics    (abstract only)   information
Abstract. We study the effects of individual's diffusion in ordering dynamics
by considering the Voter and Moran processes in a metapopulation
framework, in which individuals are endowed with mobility and
diffuse through a spatial structure represented as a graph of
patches upon which interactions take place.  We show that, in some
instances, diffusion can dramatically affect the time to reach the
homogeneous state, independently of the underlying network's
topology, the final consensus emerging through different
local/global mechanisms, depending on the mobility strength.  Our
results highlight the role of mobility in ordering processes, with
implications in the understanding of evolutionary and social
135: Romualdo Pastor-Satorras, Isabel Corominas and M. Carmen Miguel. Percolation analysis of force networks in anisotropic granular matter    (abstract only)   information
Abstract. We study the percolation properties of force networks in an
anisotropic model of granular packing, the so-called
q-model. Following the original recipe of Ostojic {\em et al.}
[Nature \textbf{439} 828 (2006)], we consider a percolation process
in which forces smaller than a given threshold $f$ are deleted in the
network. For a critical threshold $f_c$, the systems experiences a
transition akin to percolation. We determine the point of this transition
and its characteristic critical exponents applying a finite-size
scaling analysis that takes explicitly into account the directed
nature of the q-model. By means of extensive numerical simulations,
we show that this percolation transition is strongly affected by the
anisotropic nature of the model, yielding characteristic exponents
which are neither those found in isotropic granular systems nor those
in the directed version of standard percolation. The differences
shown by the computed exponents can be related to the presence of
strong directed correlations and mass conservation laws in the model
under scrutiny.
136: stefano merler and marco ajelli. Factors affecting the spread of an epidemic in Europe: population heterogeneity and human mobility    (abstract only)   information
Abstract. ********************
* Contributed Talk *

The concern regarding the emergence of a new influenza pandemic has arisen in the late Nineties when a highly pathogenic avian influenza virus capable of infecting humans was detected. In order to test the effectiveness of containing/mitigating strategies included in national pandemic preparedness plans, agent-based models have become a relevant tool and national models have been developed also for some European countries. However, Europe has never been analyzed as a whole. In this work we present an agent-based model for analyzing the interplay between the high heterogeneity of the European populations and their great mobility and how it affects the spread of an epidemic in Europe.

At country level, it is a discrete time stochastic SEIR model with force of infection depending on the distance and with explicit transmission within households, schools and workplaces. Moreover, it accounts for cross-borders diffusion, long distance travels and importation of cases from countries outside Europe. Country-specific data (e.g., on age structure, frequencies of households type and size, schools and workplaces size, school attendance and employment rates by age) are employed for modeling individuals and co-locating them in households, schools and workplaces. Data on air and railway traffic (across Europe and from abroad) are employed for modeling long distance travels and importation of cases from countries outside Europe.

When we analyze how the simulated epidemics spread (e.g., in terms of cumulative attack rate, exponential growth rate, peak day, time of the first case) in the different countries, we observe the result of two contrasting factors. On one side, the very high heterogeneity of the populations (in terms of age structure, density of population, presence of large cities or prevalence of rural areas, households
size, schools and workplaces attendance) tends to make the simulated epidemics quite different. On the other hand, the great human mobility characteristic of modern societies tends to smooth the differences by synchronizing the national epidemics and, consequently, to speed up the spread at global level.

* Contributed Talk *
137: Nicola Perra, Giancarlo Cappellini, Alessandro Chessa, Luigi Minerba and Gianni Mula. A Data Mining Approach to Health Organization Problems    (abstract only)   information
Abstract. (poster section)
Modern health care generates a vast quantity of digital data. While other large industries have capitalized on modern information technology to exploit the available data to minimize costs for a given quality target, health care industry failed to do so because of a variety of historical, political and technical reasons. Times are changing, however, and historical and political constraints are increasingly giving way to innovative approaches based on the concept of data mining.
In this study we report on a data mining analysis in which we mapped onto a complex network structure one year of standard discharge data and transactions for medical services between departments of hospitals in the region of Sardinia, Italy.
The study focused on identifying the best alternative to the existing organizational subdivision. This alternative could lead to a more efficient use of available resources, and to an improvement of the services/cost ratio. Preliminary results show that community detection techniques and Pagerank analysis developed from  complex network theory  can be a very powerful and reliable tools for mining health care databases. The implications for further research are briefly discussed.
138: Pietro Panzarasa and Bernard Kujawski. Cognitive similarity and patterns of communication: Network and content analysis of an online forum    submission   information
Abstract. Submission for contributed talk
Session theme: Networks in Organization & Communication

Cognitive similarity and patterns of communication: Network and content analysis of an online forum

P. Panzarasa and B. Kujawski

Queen Mary University of London, School of Business and Management, London, E1 4NS, UK

Research has long emphasized the role that social interaction has in the modification of individuals’ mental attitudes, meanings, and interpretations. For example, a number of empirical studies have shown that, by interacting, individuals can create equifinal meanings and shared understanding of a joint experience, revise and reconcile conflicting beliefs, and develop social norms for organized action (Bettenhause and Murnighan, 1985; Donnellon et al., 1986). However, research has often overlooked the impact that cognitive similarity among people has on the evolution of social interaction. Convergence of beliefs, interests, and interpretations can be seen not only as an outcome of interaction, but also as the cognitive antecedent that sparks the creation and dynamics of social ties. People may select each other because they share a common representation of reality, and for the same reason they may develop stronger ties with each other than with other cognitively dissimilar individuals.

In this paper, we take a step toward this direction, and investigate whether and to what extent cognitive similarity affects the likelihood and strength of social interaction. To this end, we maintain a structuralist emphasis on the network foundations of the tie creation process, but in our analysis the context that drives this process consists of a set of cognitive ties in which individuals are embedded as a result of their overlapping representations of reality. We combine network and content analysis, and infer cognitive similarities among individuals from text-based communication (Carley, 1992). We use these similarities to construct a cognitive network, and examine its effects on whether and how social interaction unfolds over time.

Data and Methods
Our analysis draws on a longitudinal network dataset from an online forum in which the users are students at the University of California Irvine (Panzarasa et al., forthcoming). The dataset covers a period of 24 weeks, from May to October 2004. The forum includes 552 groups or threads, each devoted to a discussion topic. Our study includes 1,314 users, of whom only 899 posted at least one message. A total number of 33,720 exchanged messages was recorded.

Users could belong to one or more groups, and read the messages posted by other group members. Since only users that registered for a group could read the messages posted to that group, we use group membership to identify the audience to which messages are directed. We construct the social network by assuming that a directed social tie is established from one user to another when the former posts at least one message to a group to which both users belong. The weight of a social tie from one user to another is measured in terms of the total number of characters posted by the former to all groups shared with the latter. To construct the cognitive network, for each user we recorded all words posted in the forum. Drawing on the WordNet 2.1 dictionary and its list of synonyms, for each pair of users we then measured the semantic distance among the words they posted. A cognitive tie is established between two users when there are at least two words, one posted by each user, that are semantically related. The weight of a cognitive tie between two users reflects the semantic distance between the words posted by them. Two users are cognitively but not socially connected when they post semantically related words, but do not share any group in the forum.

The evolution of the forum is characterized by a remarkable increase in the number of active users and posted messages in the first three weeks, followed by a period of stability. Most groups were created at the beginning of the observation period, and are characterized by an uneven distribution of membership. While the majority of groups only include few active users, there is a select minority with a disproportionately large amount of active members. Findings also indicate heterogeneity in the weight distributions for both social and cognitive ties. While most pairs of users are relatively weakly connected, a minority develops strong social bonds. Similarly, most pairs of users express a relatively limited amount of shared meaning, yet a minority shows a disproportionately large degree of cognitive similarity.

To investigate associations between cognitive similarity and social interaction, for each user we measured the average cognitive similarity to all other users, and for each week we found a positive correlation between this value and the user’s degree and strength measured in the subsequent week. We further estimated regression models of the probability of tie creation. Results indicate that two cognitively similar users are more likely to establish a tie with each other than a pair of dissimilar ones. We also controlled for status homophily effects, such as those arising from similarity in gender, year in college, age, region of origin, marital status, and affiliation to academic unit. Taking these variables into account does not change the results on the effects of cognitive similarity on tie creation. In addition, we examined associations between cognitive similarity and tie strength. Results show that, above and beyond the effects of status similarity, the social tie connecting a pair of cognitively similar users tends to be stronger than the tie connecting a pair of dissimilar ones.

K. Bettenhausen and J.K. Murnighan (1985): The emergence of norms in competitive decision-making groups. Administrative Science Quarterly 30, 350-372.
K.M. Carley (1992): Extracting, representing, and analyzing mental models. Social Forces 70(3), 601-636.
A. Donnellon, B. Gray and M.G. Bougon (1986): Communication, meaning, and organized action. Administrative Science Quarterly 31, 43-55.
P. Panzarasa, T. Opsahl and K.M. Carley (forthcoming). Patterns and dynamics of users’ behavior and interaction: Network analysis of an online community. Journal of the American Society for Information Science and Technology.
139: Katy Robinson, Ted Cohen and Caroline Colijn. Infection Subgraphs of Dynamic Sexual Contact Networks    (abstract only)   information
Abstract. When modelling the spread of sexually transmitted diseases, graph properties of the underlying sexual contact network - such as degree distribution, clustering and connectedness - are important factors in determining the rate at which a disease can spread. Many of these graph properties can be calculated from a static network, but knowing its dynamic properties is also important. For example, the times at which its edges exist will greatly affect properties such as the level of concurrency of relationships, or the order in which nodes can be reached.

Once such a dynamic network has been obtained, it is possible to extract subgraphs representing the nodes which can be reached by an infection starting at a given time and location. I will discuss our findings on the structure of these subgraphs and how their properties depend on behavioural assumptions and on the transmissability and duration of infectiousness of the disease.
140: Yong-Yeol Ahn, James Bagrow and Sune Lehmann. Hierarchical Link Clustering in Complex Networks    (abstract only)   information
Abstract. (Contributed talk)

Much work in complex networks research has been focused on the community structure and hierarchical organization in networks. Communities and hierarchy are often considered two aspects of a single organizing principle. However, the nodes of many networks participate in multiple contexts, such as distinct protein complexes or different types of social relationships.  This prevents a single hierarchical tree from fully encoding the hierarchy, since this tree structure prohibits nodes from simultaneously belonging to multiple, overlapping groups. Here, instead of assuming that a community is a set of nodes with many links between them, we consider a community to be a set of links that are densely interconnected. Each link is defined in a single context, allowing for a unique hierarchical tree to be constructed.  Partitioning the tree yields overlapping node communities since a node may have multiple contexts originating from its links. We apply our method to identify relevant communities in biological networks and social networks.
141: Sune Lehmann, Yong-Yeol Ahn and James P Bagrow. Link clustering using Partition Density    submission   information
Abstract. Many networks possess strong community overlap, where nodes simultaneously belong to multiple groups, preventing us from dividing them into meaningful disjoint subunits [1,2]. Locally, structure in such networks is simple. From the point of view of a single node, the communities appear non-overlapping, each community as an almost fully connected subgraph. Complex global structure emerges because each node is in this situation. The overlapping communities discussed here are distinct from "fuzzy" communities with relaxed interfaces, because overlap may exist for each node. Rather than defining a community as a set of densely interconnected nodes, we define a community as a set of (related) links. This link-centric viewpoint addresses the long-standing question of formulating overlapping community detection as an optimization problem by introducing a new objective function, the Partition Density.

[1] G. Palla, I. Derény, I. Farkas, T. Vicsek, Nature 435, 814 (2005).
[2] M. E. J. Newman, J. Park, Physical Review E 68, 036122 (2003).
142: Alexander Mehler, Matthias Dehmer and FRank Emmert-Streib. On Network Entropies : A Comparative Study    submission   information
Abstract. Information-theoretic modeling of complex networks is currently of considerable interest, see, e.g., \cite{rosvall_2008_2,sole_2004}.
The observation that complex networks are often the result of a dynamical processes leads to the insight that their analysis can not
be performed properly in a deterministic
framework \cite{emmert_streib_dehmer_2009}. Therefore, it is important to study this problem by combining graph-theoretic,
information-theoretic and statistical methods to analyze complex networks more adequately.
A special problem in this area is to characterize a complex network by taking its structural features into account \cite{dorogovtsev_2003}.
Generally, this relates to determine the structural complexity of a network, see, e.g., \cite{bonchev_book_2005,minoli_1975}.
In this paper, we put the emphasis on entropy-based measures to detect network complexity quantitatively. We interpret the resulting structural
information content of a network as the entropy of the underlying network topology.

For example, to characterize chemical graphs structurally, various information measures for graphs have been contributed \cite{bonchev_2}.
In \cite{dehmer_AMC_2007_entropy}, these measures have been conceptually generalized and applied to quantify the information content of general
networks. Advanced entropy measures to quantify
the local information
spread in gene networks representing directed scale free networks have been developed in \cite{emmert_streib_dehmer_2009}.
Also, metrical properties of graphs have been recently used to develop entropic measures of imbalance of social
ontology graphs \cite{mehler_2009}.

So far, there is no comparative study of graph entropies involving different network areas.
In this study, we determine the information content (entropy)
of networks from biology and linguistics. We show in which sense the networks of different
ontological (that is, chemical, biological, and semiotic) provenance differ in terms of their
vertex-related entropy. We use this to shed light on the relativity of laws of n
networking which differ with respect to these different areas of networking.
Last but not least we also offer a mathematical framework to formalize network-related
measures of entropy.
143: Alain Barrat, Ciro Cattuto, Vittoria Colizza, Jean-Francois Pinton, Wouter Van den Broeck and Alessandro Vespignani. High resolution dynamical mapping of social interactions with active RFID    (abstract only)   information
Abstract. We present an experimental framework to gather data on face-to-face social interactions between individuals, with a high spatial and temporal resolution. We use active Radio Frequency Identification (RFID) devices that assess contacts with one another by exchanging low-power radio packets. When individuals wear the beacons as a badge, a persistent radio contact between the RFID devices can be used as a proxy for a social interaction between individuals. We present the results of a pilot study recently performed during a conference, and a subsequent preliminary data analysis, that provides an assessment of our method and highlights its versatility and applicability in many areas concerned with human dynamics.
144: Phillip P. A. Staniczenko, Nick S. Jones and Felix Reed-Tsochas. Local trophic adaptation requires a new approach to ecological robustness and keystone species identification    (abstract only)   information
Abstract. Abstract.  Human-induced changes in the global environment are predicted to cause unprecedented rates of population and species extinction in the near future. Using a simple predator-prey switching model, we show that the incorporation of trophic link adaptation in empirical food webs can offer a new approach to ecosystem robustness and keystone species identification. This dynamic modification of local food-web topology, which allows trophic link rearrangement following species extinction, highlights the role of nestedness and omnivory in conferring robustness against secondary extinctions and network fragmentation. Using an original representation of trophic interaction data, we suggest that there are intrinsic differences between food webs regarding the additional robustness provided by trophic rewiring. Metrics based on the traditional food-web representation, such as species diversity and connectance, are unable to explain these results. Our topological representation indicates rewirings that are ecologically plausible and affords new means of identifying keystone species: in particular, those that are enablers of trophic adaptation. This talk constitutes the initial findings of our investigation of ecosystem response to the loss of biodiversity. It is hoped that this line of inquiry, whilst still preliminary, may have constructive implications for ecosystem management and conservation policy.

The increasing loss of biodiversity caused by habitat destruction, pollution, and climate change [1], has intensified our desire for a better understanding of ecosystem robustness. There is empirical support for species’ ability to adjust their feeding habits in light of environmental change: modifications can arise from adaptive behavioural [2-4] or evolutionary [5, 6] switches in food choice in response to altered patterns of resource availability. However, models based on structural approaches to food web robustness have yet to incorporate this local mechanism for ecosystem adaptation [7], and by not doing so, may underestimate robustness to secondary extinctions. We introduce a predator-prey switching model that incorporates trophic-link rewiring based on the nested nature of feeding interactions. Using this model, we subject 13 empirical food webs [8] to a variety of simulated extinction sequences. Following species extinction, links are permitted to rewire according to the ecosystem’s directed rewiring graph (DRG). We introduce this topological representation as a means of indicating rewirings that are ecologically plausible, and correspond to predators switching to non-preferred prey to allow for behavioural adaptation and phenotypic plasticity. The DRG is motivated by the phylogenetic similarity of taxonomical niches [9], with the added constraint of allowing feeding at lower trophic levels only. We use the number of secondary extinctions and the state of network fragmentation as quantitative indicators of food-web health, enabling us to identify features of the DRG that best explain the additional robustness conferred though local trophic adaptation. The presence of “adaptation enablers” (species whose prey can become accessible to other predators through an adaptive process) in the initial food web is shown to be a strong indicator of the potential for additional robustness. We can qualitatively relate food-web robustness under sequential species loss to the impact of rewiring decisions seen in the DRG using the concept of cyclic closure. This is a process whereby the rewiring of a trophic link can increase the set of potential prey available to a species for future adaptation, thus making it less susceptible to secondary extinction. This analysis suggests an ordering of cyclic closure preference that highlights the role of omnivory in enabling local adaptation to take place. Furthermore, one is able to identify particularly important omnivores that indicate the ability to feed on the prey-set of another niche-community. Other original forms of keystone species identification include the isolation of species that are crucial for the existence of specific biomass-flow routes from basal taxa to higher trophic levels. We suggest that the existence of keystone species in a dynamic sense may differ from those obtained from conventional, static, approaches. The move to considering local trophic adaptation is necessary for a more complete understanding of food-web robustness; the methods proposed here are first steps towards a new, dynamic, approach to robustness that may have implications for ecosystem management.


1. Thomas et al., “Extinction risk from climate change”, Nature 427, 145 (2004).
2. M. Kondoh, “Foraging adaptation and the relationship between food-web complexity and stability”, Science 299, 1388 (2003).
3. D. W. Stephens and J. R. Krebs, “Foraging theory”, (Princeton UP, 1987).
4. A. A. Agrawal, “Phenotypic plasticity in the interactions and evolution of species”, Science 294, 321 (2001).
5. A. Joshi and J. N. Thompson, “Adaptation and specialization in a two-resource environment in Drosophila species”, Evolution 51, 846 (1997).
6. J. N. Thompson, Trends in Ecology and Evolution, “Rapid evolution as an ecological process”, 13, 329 (1998).
7. J. A. Dunne, R. J. Williams, and N. D. Martinez, “Network structure and biodiversity loss in food webs: robustness increases with connectance”, Ecology Letters 5, 558 (2002).
8. The 13, well-studied, empirical food webs are: Bridge Brook Lake, Canton Creek, Chesapeake Bay, Coachella Valley, El Verde Rainforest, Grassland, Little Rock Lake, Scotch Broom, Skipwith Pond, St. Marks Seagrass, St. Martin Island, Stony Stream, and Ythan Estuary excluding parasites. (Courtesy of Jennifer Dunne.)
9. J. E. Cohen, “Food webs and niche space”, (Princeton UP, 1978).
145: Cecile Cartozo and Paolo De Los Rios. Extended navigability of small world networks: exact results and new insights    (abstract only)   information
Abstract. Small world networks provide a mathematical framework to explain why
any two individuals are linked, on the average, by very short chains
of acquaintances. In particular, when a regular lattice is augmented
by the addition of a few long-range connections, the average number of
steps that are needed to reach any site from any other does not
increase proportionally to the linear size of the system, but only to
its logarithm. Initially motivated by social sciences, the small-world
effect has found applications in a wide number of other disciplines
such as computer science, neurosciences and biology. Since then, an
increasing number of complex systems have been revealed to show SW
properties. Nevertheless, how real systems evolve to- wards
small-world like structures and how shortest paths can be found
without a global knowledge of the network are still open questions.

In its seminal work published in 2000, Jon M. Kleinberg studied the
efficiency of a decentralized algorithm in transmitting a message
through a particular kind of SW networks. On a
square lattice, each node is assigned a long-range connection whose lenght is selected according to an inverse
power-law distribution. At each step, the node holding the message must pass it
through one of its short or long-range connections with no knowledge
of the long-range connections of nodes that have not touched the
message yet (decentralized algorithm). Kleinberg showed that there
exist a decentralized algorithm that achieves a delivery time bounded
by a polynomial in log(N), where N is the number of nodes in the
graph, at a unique value of the power-law exponent. The algorithm is a
greedy algorithm: each node is constrained to forward the message
across a connection that brings it as close as possible to the target
in lattice distance.  In the two-dimensional case, the crucial value
of the exponent is found to be equal to 2 and the expected
delivery time T is bounded by a function proportional to (l og(N)
)^2. This result generalizes to a D-dimensional lattice for a critical value
of the exponent equal to D.

In this work, in order to compute the average delivery time
needed to reach a target at distance d, we first resort to a
formulation of the algorithm that is cast as a stochastic Markov
process. On any possible realization of the network, when the message
is at distance d from the target, at the next step it will be at
distance d'<d with a probability that depends on the probability of
having a shortcut from distance d to distance d' if d'<d-1, or
of not having it if d'=d-1. As a consequence we can write a general
expression for the average delivery time. Considering a continuos space limit of this equation, we are able to
find an exact solution for a general dimension D, that can be
discussed for the different values of the power-law exponent. The asymptotic beahviour of the expected
delivery time confirms the upper bound found by Kleinberg. We also
numerically solve the problem in one and two dimensions showing the
agreement with the theoretical prediction, for large sizes of the
146: Guillaume Chelius, Antoine Fraboulet, Eric Fleury and Jean-Christophe Lucet. A wireless sensor network to measure the health care workers exposure to tuberculosis    (abstract only)   information
Abstract. This submission is for a contributed talk.

In parallel to the advances in modern medicine, health sciences and public health policy, epidemic models aided by computer simulations and information technologies offer an important alternative for the understanding of transmission dynamics and epidemic patterns. In this paper, we focus on the first steps that may lead towards the design of epidemic models, i.e. the measure and analysis of interactions within a closed socio-professional context. More precisely, this project was motivated by the study of the Health Care Workers (HCWs) exposure to tuberculosis in their work environment.

Despite the progresses in treatment and prevention, tuberculosis remains a disease in expansion and represents the third cause of death by infectious pathologies in the world. In the health care context, if the transmission is globally controlled, the HCWs exposure remains obscure. Individual factors associated to the contamination of HCWs in their work environment are not precisely known. Our study focus on the evaluation of the intensity and the frequency of contacts between tuberculosis infected patients and HCWs. To gather this information, classical methods consist in performing audits, consulting medical and administrative files or using self-reports of conversations and trusting HCW souvenirs. All these methods are time-consuming, subject to memory failures and interpretations. As an alternate method, we have chosen to dedicate a Wireless Sensor Network (WSN) to gather these interactions inside a Service of Infectious and Tropical Diseases (Bichat-Claude Bernard Hospital, Paris) and a Service of Pneumology (La Pitié Salpétrière Hospital, Paris). Within the two services, each room has been equipped with a sensor node and each HCW carries an autonomous sensor during his presence in the service. An important characteristic of this measurement campaign is that it was performed in a closed environment, over a closed population and during a large continuous period of time. That is, the presence of all HCWs of the units was monitored in all patient rooms, 24/7 during a three months period. In addition to the experimental measure system description, this paper main contributions are the analysis and characterization of this huge and unique data set describing a complex dynamic interaction network, and the impact study of the measurement process bias on the network dynamic. The analyze of large dynamic in situ interaction networks provides an opportunity to study dynamical processes occurring on dynamical networks, such as spreading or epidemical processes, taking into account the dynamics both on and of the network structure.
147: Graham Williamson, Davide Cellai, Simon Dobson and Paddy Nixon. Poster: Data dissemination on human proximity networks    (abstract only)   information
Abstract. Networks with a dynamic topology have arisen interest in several disciplines such as biology, social and information science. In computer science, new communication protocols named delay tolerant networks (DTN) have been designed for highly dynamic networks, such as mobile ad hoc networks, or networks embedded in a challenged environment, as the space [1]. An important example of those systems is the network formed by the proximity of people carrying devices which communicate directly with other devices within a short range [2]. On the other hand, a recent study has focused on a large data set of mobile phone calls and uncovered characteristic patterns of human mobility [3].
We thoroughly investigate the network of human proximity observed in experiments and define new dynamical properties able to characterize the capability of the network to support message delivery. We find significant correlation between different notions of centrality and dynamical quantities that only involve local information, such as the number of encounters a node experiences in a typical time scale. We also simulate a model of mobile agents to discuss the generality of the observed behaviour of the network at larger scales. Finally, we propose a new communication protocol which exploits common patterns of human mobility networks and allows efficient delivery without global network informations.

[1] K. Fall, in SIGCOMM ’03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications (ACM, New York, NY, USA, 2003), pp. 27–34, ISBN 1-58113-735-4.
[2] A. Miklas, K. Gollu, K. Chan, S. Saroiu, K. Gummadi, and E. de Lara (2007), pp. 409–428, URL\_24.
[3] M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabasi, Nature 453, 779 (2008), URL
148: Floriana Gargiulo. The diffusion of innovative ideas in dynamical scenarios    (abstract only)   information
Abstract. The  diffusion of innovative ideas in  social frameworks has been the object of studies relevant for  many different disciplines. Different mechanisms for the diffusion can be considered on many  typologies of social structures. Some classes of problems regarding the innovation spreading can be described with the Abram-Strogatz formalism, a model introduced for linguistic diffusion but extendible to other mechanisms of social contamination processes.   
On the other side, recently a big attention has been given to co-evolving networks: structures where the topology of networks changes continuously, adapting to the intrinsic characteristics of the nodes (for example, the opinion) .
I consider a dynamical network, where the links evolve according to the cultural traits of the single nodes, giving rise to variable groups and communities sharing the same behavioral norms. In this dynamical framework the diffusion process of an innovative idea is studied.  It is analyzed how the introduction of  an evolutionary  network background can change the scenario obtained for Abram-Strogatz model of innovation diffusion.
149: Takashi Iba and Satoshi Itoh. Sequential Collaboration Network of Open Collaboration    (abstract only)   information
Abstract. (Abstract for Oral Presentation)

In this presentation, we propose the method of sequential collaboration network for capturing the feature of open collaboration with the case of Linux and Wikipedia. Open collaboration is the action of cooperation by people who are connected on World Wide Web over region or organization, which brings added-value which can not be achieved by one. In community that successfully operates the process of creation through collaboration, communication gains “momentum,” and it sympathizes and amplifies in a nexus. Along with this effect, connecting the path of communication one by one, it is possible to bring up unexpected remarkable idea and innovation. In our research, the nexus of communication is described as sequential collaboration network, where each collaborator is drawn as a node, and the nexus of communication is drawn as a link between the nodes. In our presentation, two cases will be shown: Linux and Wikipedia. First case is open-source development of Linux, which is an operating system developed as open-source software, based on the logged text of mailing lists and newsgroups. Second case is editing articles on Wikipedia, which is an online encyclopedia written by open-collaborators.
150: Kathryn Cooper and Mauricio Barahona. Role Similarity Clustering on Directed Networks    (abstract only)   information
Abstract. (Submission for Poster)

We consider the problem of clustering on directed networks with an alternative approach.  In contrast to traditional clustering, which is based upon density of connections, we choose to group vertices that play a similar role within the network. The method reveals interesting insights on data from ecology, world trade and metabolic networks.
The majority of initial network research to date has focused on simple, unweighted, undirected graphs. Including edge direction is crucial to understanding the structure in many cases.
We speculate that the function of a node will be reflected in the pattern of connections and vertices with the same function may not in general be close in a network sense.  The identification of functionally similar nodes has implications such as the ability to assign a function to uncharacterized nodes, or to simplify a network into a coarse-grained structure.
We also extend the idea to the problem of finding and clustering functionally similar nodes in two different graphs.  This leads to a method for identifying graphs with comparable underlying structures.
This work draws examples from world trade, ecology and metabolic networks as proof of application potential.  Our method detects plausible trophic levels within example food webs.  Initial results from world trade networks are consistent with previous core-periphery structure theories from the social sciences.  Additionally, we shed light on a possible core-peripheral structure of metabolic networks across species.
151: Nicola Perra, Vinko Zlatic, Alessandro Chessa, Claudio Conti, Debora Donato and Guido Caldarelli. Localization of the PageRank in the WWW as disordered potential problem    (abstract only)   information
Abstract. (contributed talk)
The World Wide Web is one of the most important communication systems we use in
our everyday life.  Despite its central role, the growth and the
development of the WWW is
not controlled by any central authority. This situation has created a
huge ensemble of connections whose complexity can be fruitfully
described and quantified by network theory. One important application
to sort out the information present in these connections
is given by the PageRank algorithm. High PageRank values signal the
presence of important web sites. In this paper we show how these
maxima of the PageRank can be regarded as a localization phenomena. We
were able to rewrite the original iterative PageRank equation in a new
non iterative form, in which we can define a wave function related to
the PageRank value and a potential function connected to the
topological features of the network.
We show that the topological disorder given by the unbalance of
outgoing and ingoing links between pages, induces wave function and
potential structuring. This allows to directly localize the pages with
the largest score. Through this new representation we can now compute
the PageRank without iterative techniques.
Our results also clarify the role of topology in the diffusion of
information within complex networks.
152: Kamil Rakocy, Jan Zajac and Andrzej Nowak. Modelling the diffusion of epidemic considering change in behaviour. The case study of Poland    (abstract only)   information
Abstract. Introduction
The existing models of infectious diseases emphasize inevitability of pandemics, yet they do not take into consideration the dynamic nature of social behaviour. We use dynamical network approach and multi-agent simulation to examine how the classical SIR model of epidemics changes when effects of media coverage are considered. The latter influence behaviour such as social contacts, internal migration and fleeing and in consequence modifying the probability of contact and infection.

In our model high granularity data on commuting and travelling in the whole country gathered by road transport authorities are included. Moreover, the SIR model is validated by medical statistics on number of influenza cases in each county. Additionally, data concerning change of behaviour as effect of exposure on information about pandemic was collected in 2 surveys.
The data regarding social behaviour is based on 2 sources: general national representative survey (CAPI; N=18 000) and more specific Web survey (N=3 000), with manipulation regarding distance from the site of epidemics.

We take a class of small-world networks as a basis for modeling to create data driven model. We improve current model enabling modifications of transport networks (evolution of weighted network) and therefore flows of people between locations as the epidemics spreads.

An instant messenger communication network, with high resolution (aggregated on county level) is used to compare with travelling network. This mix of network and survey data enable us to test influence of different strategies of prevention and mass media communication on epidemic spread.
153: César Hidalgo, Nicholas Blumm, Albert-László Barabási and Nicholas Christakis. The Phenotypic Disease Network    (abstract only)   information
Abstract. For contributed talk.

The use of networks to integrate genetic, proteomic, and metabolic datasets has been proposed as a viable path toward elucidating the origins of specific diseases. Here we present a phenotypic database summarizing correlations obtained from the disease history of more than 30 million patients in a Phenotypic Disease Network (PDN). The dataset (available at represents the largest relational phenotypic resource publicly available. We present evidence that the structure of the PDN is relevant to the understanding of illness progression by showing that (1) patients develop diseases close in the network to those they already have; (2) based on the network structure we may generate a ranked list of a patient's potential future diseases; and (3) diseases highly connected in the PDN tend to be more lethal than less connected diseases. Our findings [1] show that disease progression can be represented and studied using network methods, offering the potential to enhance our understanding of the origin and evolution of human diseases.

[1] Hidalgo, Blumm, Barabási, Christakis, 2009 A Dynamic Network Approach for the Study of Human Phenotypes. PLoS Comput Biol.
154: A. V. Goltsev, F. V. de Abreu, S. N. Dorogovtsev and J. F. F. Mendes. Stochastic model of neural networks    (abstract only)   information
Abstract. (Contributed talk)
Based on recent experimental investigations and ideas of dynamical cellular automata, we develop a new class of models of neural systems with excitatory and inhibitory neurons and a complex network architecture. This model uses simple stochastic rules to govern the dynamics of interacting neurons. It takes into account both spontaneous activity, external stimulation, and neural pacemakers. We derive rate equations which describe the evolution of global activities of the neural populations activated by either an applied stimulation or neural pacemakers. These equations are exact in the case of infinite sparse uncorrelated networks with arbitrary degree distributions, though for brevity, we present results only for classical random graphs. The proposed model has a complex phase diagram with self-organized active neural states, hybrid phase transitions, hysteresis and a rich repertoire of activities including decaying and stable oscillations, stochastic resonance and avalanches. We also show that if spontaneous activity of neurons overcomes a critical threshold then, in a certain range, stable oscillations in the activities of the neural populations emerge. Sharp stochastic resonance precedes the transition to this regime. Theoretical predictions were confirmed by simulations of stochastic dynamics of the model. Our simulations revealed that even small networks with 50-1000 neurons display oscillations similar to large networks. We suppose that in the regime with oscillations, neurons are synchronized more strongly than in regimes without oscillations. This probably enhances the robustness of oscillations against stochastic effects in neural networks.
155: Fabrizio Lillo, Rosario N. Mantegna, Jyrki Piilo and Michele Tumminello. Network of investors acting in a financial market    (abstract only)   information
Abstract. We analyze a rather unique database providing the coded information about the daily stock ownership of all Finnish investors who are investing in a given stock. Specifically, we study the pattern of investment of all Finnish investors trading a set of stocks at the Helsinki Stock Exchange and in Stock Exchanges at least for twenty days during the period from 09/1998 to 12/2003. The database contains information about all investors, and they are classified in six major groups. These groups are Companies, Financial institutions, General Government Institutions, No Profit Institutions, Households, and Foreign Institutions. Investors are very heterogenous with respect to both the frequency of trading and the volume of activity. For this reason an analysis performed at the level of single investor is difficult to achieve. In fact previous investigations [1] of the present database have considered aggregated variables characterizing groups of investors. Analyses of the correlation between inventory variation profiles, similar to those performed in ref. [2] to describe the activity of market members trading at the Spanish stock exchange, are also not feasible at individual investor level due to the large amount of heterogeneity present in the investors' activity. To investigate this system at the level of single investors we therefore move from the analysis of continuous variables, like the inventory variation, to the investigation of categorical variables associated with the investor's activity during single days: buy, sell, or both buy and sell. By using categorical variables and a statistical validation method used in biostatistics [3] we construct a network between actions (buy, sell, buy-sell) of each couple of investors. Links between actions of investor pairs are statistically validated against a null hypothesis of random co-occurrence by using a 1% p-value threshold corrected for multiple comparisons (so-called Bonferroni correction). The detected network includes 637 elements describing the categorical activity of 402 different investors. After detecting communities in the network [4], we find groups of investors characterized by a similar activity profile. The most prominent group is a set of heterogeneous investors either buying or selling with high daily synchronization. We also detect a set of investors who use a contrarian strategy triggered by the synchronous return of the traded stock. The composition of the different communities of investors in terms of investor classification, e.g. companies, households, etc. is usually heterogeneous. For instance, financial institutions are present in several groups, but their action profile is strongly dependent on the specific group they belong to. This is the first attempt to describe the network of investment profile of a heterogeneous set of individual investors.


[1] Grinblatt M. and Keloharju M., The investment behavior and performance of various investor types: A study of Finland's unique data set.  J. Financ. Econ. 55 43 (2000).
[2] Lillo F., Moro E., Vaglica G., Mantegna R.N., Specialization and herding behavior of trading firms in a financial market, New Journal of Physics 10, 043019 (2008).
[3] Draghici S.,  Data Analysis Tools for DNA Microarrays. Chapman & Hall. CRC press (2003).
[4] Duch J, Arenas A, Community detection in complex networks using extremal optimization, Phys. Rev. E 72, 027104 (2005).
156: Ben Collingsworth and Ronaldo Menezes. Temporal Email Network Analysis as an Early Indicator of Organizational Tension    (abstract only)   information
Abstract. Poster Submission

Large social networks tend to be very robust in their structural
characteristics. If we look at patterns of email activity in an
organization, we expect the network to be kept very stable
overtime. This assumption can be confirmed by looking at the fact that
the stream of email for people do not change very often except when
there are special circunstancies. Even when there is such an increase
in message flow, the pattern of these messages tend to be the same,
meaning that people send messages to the same people they send message
every day (on average). The question then becomes wheather changes in
the network characteristics be serve as an early indicator of unrest
in the organization body. In our study we construct a network of the
Enron email logs and show that anomalies can be detected at the
network level in properties such as clustering coefficient and
homophily. What we argue is that these anomalies are an indication of
unrest that may lead to problems in the organization.  In our study we
correlate the anomalies with events in the history of Enron from a
time of high moral (when the stock price was very high) to a period of
almost desperation (when all employees lost their jobs). The argument
in our study is that the anomalies in the network preceed the events
because people radically change their behavior. For instance, social
sciences indicate that in hard times, people tend to cling more to
their friends and friends (increase in homophily). Hence one can build
tools to detect such changes and provide early warnings to interested
157: Roozbeh Manshaei, Pooya Sobhe Bidari, Amir Feizi, Javad Alirezaie and Mohammad Ali Malboobi. Modeling of Gene Regulatory Network Using a Novel Neuro Fuzzy Network Algorithm    submission   information
Abstract. Genetic networks provide a concise representation of the interaction between multiple genes at the system level, giving investigators a broader view of the cellular state compared to a singular declaration of whether a gene is over or under expressed. In the last few years, with the advent of microarray techniques, modeling and analyzing of dynamic properties of biological networks has been one of the most hot spot in modern biology. Biologists now have the ability to investigate the expression of genetic transcripts on a genomic scale. It is noticeable that modeling of gene expression faces with the serious problem such as noisy data in expression experiments and insufficient number of data point. These problems resulted in difficulties in understanding of genetic networks dynamics on a larger scale. So, many of the researchers intended to work on the sub-networks that are loosely connected with other part of the networks and are modular. This could help with extracting the general dynamic rules in biological networks and more carefully modeling of large scale data dynamics. Consequently, examining and designing of optimum algorithms that models these sub-networks play a vital role in switching from sub-network to network dynamic modeling.
Many algorithms currently have been developed to construct genetic networks from gene expression data, including Boolean Networks, Bayesian Networks, Weight Matrices, Differential Equations Models, Causal Inference, Graphical Gaussian Models, Partial Least Squares and Fuzzy Logic Models.
We also have tried to find and improve a new algorithm for better modeling of genetic networks. Our approach uses a novel neuro fuzzy structure to extract information from time-series gene expression data from microarray experiments.
We ran the our proposed algorithm model on the gene expression values corresponding to selected twelve genes from the yeast cell-cycle pathway, and checked for consistency of the estimated network with the pathway depicted in KEGG. The results presented here have been simplified by indicating all positive interactions with a 1, all negative interactions with a -1, and no interaction with a 0.
Knowledge of a whether a connection exists, though, is still useful to biologists, who can design further assays to study the nature of the interaction between the genes. Hence, the ability of an algorithm to correctly specifying an existing edge, regarding to direction, is important. In this case, the proposed algorithm captures 73% of the edges between genes.
158: Jason Boorn. I'm Like You, Just Not in That Way: Trust Networks to Improve Collaborative Filtering    (abstract only)   information
Abstract. Collaborative filtering aims to predict a person's preferences by examining the preferences of similar people, in effect establishing a network of preferences.  By necessity, many existing collaborative filtering algorithms rely on a coarse notion of similarity, a notion which assumes we can compare two people in terms of taste the same way we might compare them in terms of height or shoe size.  Specifically, it assumes that if I like enough of what you do in a few specific areas, I am likely to make good recommendations for you in other areas.  In fact, trust in this case is rarely implicit; more often we tend to trust recommendations from certain people in certain areas.  

In this paper we introduce a notion of trust which reflects this quality.  Rather than capturing taste information at the user level, we capture taste at the topic level by considering groups of items given a common tag.  A tag is a small word or phrase which can be attached to an item for categorization purposes.  We find that employing trust by topic provides a significant improvement in the accuracy of recommendations without a commensurate loss in coverage.  Also, this notion of trust gives rise to preference networks which display interesting properties.  These networks can be exploited to further improve recommendation results, and we investigate several possibilities which are inspired by recent research in graph theory.

We test the theories above on a data set from CiteULike, a social recommendation system for researchers.  This site allows researchers to save and tag articles of interest.  Although the CiteULike data set has been used extensively in collaborative filtering research, we find that the raw data suffers from a significant spam problem.  Part of our study involves an investigation of how this spam changes the character of the data set and the shape of its associated graph.
159: Gareth Baxter and Marcus Frean. Mutation and Selection on Graphs    (abstract only)   information
Abstract. (Contributed Talk)

In an evolving population, network structure can have striking effects on the survival probability of a mutant allele and on the rate at which it spreads. In networks with ‘hubs’ (representing geographic or other constraints), the heightened probability of success of an initially rare mutant has led to the prediction that such networks act to amplify the effects of selection over drift. However, selection and mutation interplay in a subtle way in such populations: hubs also slow the mutant’s rate of invasion, so that if multiple mutants are allowed to spread at the same time, more of them may be present.

We describe a simple extension to the usual Moran-like model for evolution on networks, in which we take account of ongoing evolution rather than following a single mutant to fixation. Mutations are introduced at a steady rate, and eventually an equilibrium between mutation and selection is reached. The population mean fitness and variance, and the time taken to reach the steady state depend on the network structure, the population size and mutation rates.
We find that in this model the amplifier effect is largely reversed: for much of the parameter space networks with hubs suppress rather than amplify selection. This is explained by considering the relative time scales of mutation and selection. We also examine the strong effect that invasion-order has in such models.
160: Amir Feizi, Roozbeh Manshaei and Pooya Sobhe bidari. Evolutionary Network Biology: Constrains and Future Prospective    submission   information
Abstract. After the revolution of molecular biology in 1980s, the fact was straightened that phenotype is the result of the dynamic interaction between genome and its products with the environment. Nevertheless, we are in the opening of answering to the questions such as how we can link between the reflection of evolutionary events in the biological networks with the macroevolution and how genome talks with the environment to select the optimum changes in microstructures and networks. It seems that many of the evolutionary concepts discussed on the phenotype such as fitness and convergent/divergent evolution have many complexities in the genomic and network level. So, for resolving the complexity of biological networks evolution we have to use divide and conquer like procedures.Investigations have shown that regarding to dynamic characteristics of biological networks, the wiring is more important than dynamic details. In other words, it is speculated that the modularity and conservation of functional motifs in biological networks should have been evolved through the evolution, as cells need to work as a system. This point could be a match point between recent studies in network biology and systems biology that the former works on the statistical and quantitative properties and the later works on dynamic aspect of large and small biological networks.
Recent analyses also have been succeeded in revealing evolutionary conserved motifs and circuits in both structural and dynamic behavior of biological networks and these findings are in accord with the functional data. In addition, considering dynamics on networks neglecting details in an abstract level have been useful in obtaining architectural information about the networks. In regard to these advances, there are many constrains in our ongoing way including: uncertainty of high throughput techniques outputs, undiscovered proteins interaction, whole and segmental genome duplication fate on biological networks and conceptual difficulties of natural selection affect in network level.
In accord with these constrains, some frontier researches recently have proposed number of models in tracing evolutionary aspect of whole and segmental genome duplication affect on biological networks. So far, the weakness of these works is that many of them rely only on statistical properties of protein-protein interaction in a single organism while protein networks in various kingdom organisms may have their specific evolutionary scenario. For example, whole genome duplication is more frequent in plants due to their widespread polyploidy; and it seems plant networks have gained specific evolutionary mechanism for their network expansion and evolution. Although, it is acceptable that we have to explore evolution of biological networks at sub-network level for reducing the complexities, yet the most vital issue is that many of the evolutionary events occurred at least in euchromatin are in the selection force regarding to their products interaction as a building blocks in structural and functional features of cellular systems. For the future work, it is necessary to progress in multiple networks alignment of organisms from different kingdom in small and large scale to better measuring of evolutionary concept in network level
161: Masashi Iwakami and Takayuki Ito. Analyzing Network Structure of Borrowers and Lenders in Social Lending    (abstract only)   information
Abstract. Social lending is, in its broadest sense, a certain breed of financial transaction (primarily lending and borrowing) that occurs directly between individuals without the intermediation or participation of a traditional financial institution. Analyzing a network of borrowers and lenders in social lending is important for finding communities to which good borrowers belong and trends of how to lend money. Social lending has a social network service on its system and thus users interact mutually using relations such as friendship. Users also form a network whose nodes are users and edges are loan relations. In these networks, finding correlations between user communities and loan communities will clarify the fact what kind of communities produce good borrowers and what kind of borrowers lenders tend to lend money to. These facts are crucial for owners because they can apply to recommendation of borrowers and creating portfolios. This paper clarify the characteristics of networks in social lending for analyzing social networks obtained from
163: Joao Oliveira and Alexei Vazquez. Impact of interactions on human dynamics    (abstract only)   information
Abstract. Contributed poster:

Queueing theory has been recently proposed as a framework to model the heavy tailed statistics of human activity patterns. The main predictions are the existence of a power-law distribution for the interevent time of human actions and two decay exponents $\alpha=1$ and $\alpha=3/2$. Current models lack, however, a key aspect of human dynamics, i.e. several tasks require, or are determined by, interactions between individuals. Here we introduce a minimal queueing model of human dynamics that already takes into account human-human interactions. To achieve large scale simulations we obtain a coarse-grained version of the model, allowing us to reach large interevent times and reliable scaling exponents estimations. Using this we show that the interevent distribution of interacting tasks exhibit the scaling exponents $\alpha=2$, 3/2 and a series of numerable values between 3/2 and 1. This work demonstrates that, within the context of queueing models of human dynamics, interactions change the exponent of the power-law distributed interevent times. Beyond the study of human dynamics, these results are relevant to systems where the event of interest consists of the simultaneous occurrence of two (or more) events.
164: Antonio Santiago, Juan Pablo Cárdenas, Ana María Tarquis, Juan Carlos Losada, Florentino Borondo and Rosa M. Benito. Heterogeneous complex network formalism. Application to porous structure of soils    (abstract only)   information
Abstract. We present a general formalism for models to study the evolution dynamics of complex networks [1]. It is an extension of the preferential attachment model to heterogeneous networks (HPA), which we define as those where nodes have intrinsic properties that bias their attachment probabilities to other nodes. We would like to emphasize that the proposed class of models is quite general and contains most of the previous heterogeneous network models available in the literature, including the fitness model, as particular cases. Also it should be mentioned that although there are some previous models that incorporate an internal property to nodes (e.g. hidden variables), none of them focuses on growing networks with such heterogeneity.

An analytical expression of the degree distribution has been derived for the general class of heterogeneous models presented [2]. It has been shown analytically that all the models in this class present power laws in the degree distribution with different exponents.

We have also carried out a numerical simulation of the degree distribution and clustering in the threshold model [1]. This is a particular case in the class of models proposed, where the attachment affinity is inversely related to the distance between node states as given by a space metric. This particular model is introduced in order to provide a benchmark for numerical simulation of heterogeneous networks, while loosing as little generality as possible in the choice. We think that the hypothesis of an inverse relationship between affinity and intrinsic distance (as given by a relevant metric) may be a reasonable proxy for many real networks where preferential attachment can be considered as the most relevant linking mechanism.

Finally, as an example we present an application of the HPA model to quantify the structure of porous soils [3]. Under this perspective pores are represented by nodes and the space for the flow of fluids between them are represented by links. Pore properties such as position and size are described by fixed states in a metric space, while an affinity function is introduced to bias the attachment probabilities of links according to these properties.

[1] A. Santiago and R. M. Benito, “Emergence of multiscaling in heterogeneous complex networks”. Int. J. Mod. Phys. C 18, 1591 (2007).

[2] A. Santiago and R. M. Benito, “An extended formalism for preferential attachment in heterogeneous complex networks". Europhys. Lett. 82, 58004 (2008).

[3] A. Santiago, R. M. Benito, J. P. Cárdenas, J. C. Losada, A. M. Tarquis and F. Borondo, "Multiscaling of porous soils as heterogeneous complex networks". Nonl. Proc. Geophys. 15, 1-10 (2008).
165: Andrea Apolloni, Karthik Channakeshava, Lisa Durbeck, Maleq Khan, Chris Kuhlman, Bryan Lewis and Samarth Swarup. Diffusion of Information Through Private Communication in  Realistic Social Networks    submission   information
Abstract. Please consider this for a "contributed talk"
166: Cristina Martelli and Stefania Rodella. Networking administrative data(bases): a common good for public memory, a public policy for transparency and democracy    (abstract only)   information
Abstract. Modern societies are largely based on social and economic networks and decisionmaking processes are increasingly consistent with a governance approach, taking into account different perspectives and multiple stakeholders. Consequently, public information systems need increasingly complex descriptions and should experience continuous development, in order to appropriately integrate system’s observers, conveniently describe dynamic competitive structures and sustain democratic processes, also allowing impact assessment and evaluation of policies.
Administrative data, generated along the real life processes, are particularly useful for complex systems representation but, up to now, their usage has been frustrated by the heterogeneity of semantics adopted by the entities acting in the contexts under observation. In this work we intend to describe some methodological issues and concrete strategies adopted to build complex information systems supporting governance in health and healthcare fields. Usually these problems are faced by searching solutions mostly through the adoption of technological strategies: in this work we will rather focus on linguistic and semantic issues, exploring the role that conceptual models can play to organize the required knowledge, in order to find and create suitable information sources. Actions directed towards an effective harmonization of multiple semantics will be proposed and discussed.

Proposed field: Contributed talk in 'Networks in Organization & Communication' or 'Networks in health and society'
167: Maximilian Schich. Evaluating Cultural Heritage Databases Using Degree Matrices    (abstract only)   information
Abstract. In current practice cultural heritage databases, such as library catalogues, museum inventories and research databases, are often evaluated - and subsequently funded - based on their initial data model and their number of records, i.e. the number of nodes entered into the system. However, like in other databases, data models and processing rules are subject to a priori definitions, which are subsequently combined with the local activity of data entry personell and the heterogeneity of the data itself – resulting in a complex data structure. As a consequence the classic evaluation criteria – standardness of the data model and number of records – turn out to be problematic, as both criteria do not take into account, the emerging complexity of the database as a whole.

In this paper we propose a way to visualize the emerging complexity of cultural hertitage databases by focussing on the distribution of their links – facilitated by the fact, that most link relations in these databases turn out to be scale-free and self-similar in nature.
In particular we propose the use of degree matrices as an idicator of how the data fits into the a priori data model. Mapping a number of databases to a standard data model, such as the CIDOC-CRM, this also allows for easy comparison of databases, indicating both focus as well as bias of particular projects, enabling better judgement on behalf of the evaluators.

The construction of our proposed degree matrices is simple: First, the data model is visualized as an adjacency matrix – as opposed to the regular wire diagram or node-link representation, which is usually used in database administration. Whereas in the wire diagram node types are depicted as boxes and link types as lines, in the adjacency matrix, each node type is represented as a row and column, and each link type between two node types is represented as a matrix cell. As a consequence we can place the degree distributions of all existing link types in the adjacency matrix, resulting in a joint visualization of the a priori data model and the heterogeneity of data in the database.
The method scales well to even very complicated data models: Multiple link relations between two node types can be represented in the same matrix cell, while visually separating them in different ways. Data models with a large number of node and link types can usually be reduced easily to a meaningful size, as the number of links per link type is usually also scale free.
168: Alejandro Morales Gallardo and Dirk Brockmann. Network-network duality - The impact of social network structures on metapopulation models for disease dynamics    (abstract only)   information
Abstract. We introduce a novel theoretical framework that reconciles the two most prominent modeling paradigms for disease dynamics: metapopulation models and contact network models. While metapopulation models account for spatial inhomogeneities in population dynamical systems, they assume homogeneous interactions within their communities. Contact network models, on the other hand, account for individual variability, yet typically ignore spatial structure. Here, we investigate the impact of the combination of individual contact patterns and metapopulation community structure on the dynamics of epidemic processes. We set up a metapopulation structure where individuals are placed and interact by means of heterogeneous contact rates and their contact network across communities. We derive an individual-level interaction term in an operational fashion. Our results show that for a constant population contact rate, infectious diseases become more sensitive towards epidemic outbreaks as the probability of direct links between individuals decreases. This could be of relevance in systems that deviate substantially from the well-mixed assumption. Outbreaks also become more volatile if the variability of the population contact rates increases.
169: Elizabeth Leicht and Raissa D'Souza. Percolation on interacting networks (contributed talk)    (abstract only)   information
Abstract. The past decade has seen significant advances in understanding the structure and function of networks.  The majority of past work has focused on the study of individual networks treated as independent systems.  However, many real networks are just one component in a much larger complex system; a system that can bring together multiple networks with distinct topologies and functions.  In these systems of networks, direct interactions between elements distributed amongst different networks are distinct from intra-network interactions between elements in the same network.  Here we develop a mathematical formalism for interacting networks using on both intra- and inter-network connectivity properties.  We derive exact expressions for the percolation threshold describing the onset of large-scale connectivity in systems of interacting networks. We show that the percolation threshold in an individual network can be significantly lowered once  "hidden" connections to other networks are considered.
170: Detlef Holstein, F. V. de Abreu, S. N. Dorogovtsev, J. F. F. Mendes and A. V. Goltsev. Simulations of stochastic dynamics of a neural network model    (abstract only)   information
Abstract. (Poster)
We present results of comprehensive simulations of a model of neural networks which consists of two types of neurons, excitatory and inhibitory neurons. In simulations we use simple rules to govern the stochastic dynamics of these neuron populations. We take into account spontaneous activity, external stimulation, neural pacemakers, and interactions between neurons. We present results for neural networks on directed classical random graphs and the static model of complex networks with a scale-free degree distribution. We obtain the phase diagram of self-organized active neural states in dependence on the concentration of inhibitory neurons, the mean degree, the value of the threshold of the post-synaptic potential, and activation and deactivation rates. Our simulations demonstrate that with increasing the external stimulation, the activation process has a jump at a critical point as at a first order phase transition if the concentration of inhibitors is less than a critical value. At larger concentrations there is no phase transition. We also present numerical results on hysteresis phenomena, decaying and stable oscillations for neural networks. Our simulations support the theoretical results. The larger the size of the network the better the agreement. Our simulations also reveal interesting stochastic fluctuations which depend on the size of the network. We discuss the origin of these fluctuations, their relationship with the clustering and feedback loops.
171: Dale Hunscher. Utilizing Network Visualization to Assess the Quality of Online Consumer Health Search    (abstract only)   information
Abstract. The World Wide Web provides access to vast quantities of health information to the general public. An increasing proportion of consumers access this information via "organic search", submitting textual queries to a commercial search portal. Moreover, consumers now place more trust in information they find online than they place in the advice of their primary care physician and other health professionals with whom they have contact. For these reasons, the quality of search engine results is growing in importance from a public health perspective. Highly reputable non-commercial sources, including but not limited to national health services and academic health centers, maintain extensive Web sites aimed at providing information consumers can understand and use to better understand and manage their own health concerns. Major commercial health information portals have the same humanitarian aims and provide substantial breadth and depth in the content they serve. However, some commercial online health information portals seem to be little or no substantive content while bombarding the site visitor with advertising. Virtually all commercial sites are supported by advertising revenues, calling into question the objectivity of even the most reputable among them.

Methods in common use for assessing the quality of search engine results involve considerable manual effort and produce soporific quantities of tabular data or nearly-opaque statistical measures.  Network visualization can provide a more lucid and compelling alternative, enabling facile comparison of the effects of differently phrased queries on result set quality, as well as comparison of the quality of results for different health topics. This poster illustrates a network analysis and visualization technique that combines a data-driven click prediction algorithm with categorization of commercial search engine results by top-level domain (e.g., .com, .gov, .int, etc.), providing intuitive insight into the availability of consumer health information provided by government and academic sites vis-a-vis their commercial competitors. The visualizations show that access to reliably objective consumer health information depends heavily on the topic under investigation, and on the phrasing of queries for any given topic.
172: Andrzej Nowak, Wieslaw Bartkowski and Robin Vallacher. Dynamics of evaluation in the construction of shared reality    (abstract only)   information
Abstract. Information isn’t hard to come by in today’s world. Evaluating that information, however, is a daunting task for individuals, groups, and institutions. How do you determine which information is important? How do you resolve conflict among different pieces of information? How should you assemble information into a meaningful higher-order structure? These are difficult enough issues for the individual; their difficulty multiplies when a group must coordinate individuals’ decisions and act on the basis of socially validated information.
Research in social psychology suggests that individuals interact, in large part, to construct a shared reality that consists not only of shared information, but also of agreed-upon opinions. In this process, they don’t simply transmit information. More importantly, they influence one another to arrive at a common interpretation of information. In fact, two different processes occur in social networks, information transmission and social influence. The dynamics of each of the process is affected by different structural properties of networks.  We aim to supplement the social-network perspective by incorporating mechanisms of evaluation that is governed by social influence.
Numerous experiments in social psychology have shown that three critical factors determine social influence’s impact: the number of sources exerting the influence, the sources’ immediacy to the targets, and the sources’ strength. We can describe these variables’ joint effect in terms of dynamic theory of social impact. Whether the issue is conformity, stage fright, or interest in news events, influence grows approximately as a square root of the number of people involved, decreases with the square of the distance between the source and target, and is proportional to the sources’ strength (for example, social status or credibility).  
Computer simulations with rules based on empirical results investigate the dynamics of evaluation in social networks.
173: Diego Garlaschelli, Tiziano Squartini and Maria Loffredo. Generalized Bose-Fermi statistics and structural correlations in weighted networks    (abstract only)   information
Abstract. (Contributed Talk):

We derive a class of generalized statistics, unifying the Bose and Fermi ones, that describe any system where the first-occupation energies or probabilities are different from subsequent ones, as in presence of thresholds, saturation, or aging. The statistics completely describe the structural correlations of weighted networks, which turn out to be stronger than expected and to determine significant topological biases. Our results show that the null behavior of weighted networks is different from what previously believed, and that a systematic redefinition of weighted properties is necessary. We propose a solution to the problem through a straightforward unbiased generalization of unweighted quantities to weighted networks.

[1] D. Garlaschelli and M.I. Loffredo, Phys. Rev. Lett. 102, 038701 (2009).
[2] T. Squartini and D. Garlaschelli, Preprint (2009).
174: Marta C. Gonzalez and Laszlo Barabasi. Mobility Networks    (abstract only)   information
Abstract. It is my goal to establish a
link between measurements on human motion and epidemic spreading
models. I am focused on the detection of laws that provide a
coarse-grained description of the number of travels between places
(e.g.  municipalities or counties). It has long been posited that
different types of interaction between geographical locations decline
with increasing distance (time, cost) between them, but is positively
associated with the amount of activity at each location.

In an analogy to Newton's law, Gravity Models are often used in
transportation planning to illustrate the macroscopic travels between
places.  The usual data used to feed these models are gathered from
census on commuting behavior. Some of the drawbacks of gravity models
is the lack of a mechanistic formulation that provides insights to
understand the family of parameters needed to fit different
datasets. One of the questions I would like to focus on is: Is there
an optimal scale for which there are universal laws of travel between
places?.  With such an aim I want to investigate how massive data on
mobile phone information can be used to provide insights in this area.
I will determine whether mobile phone information on aggregated
travels is related with other sources of information, such as census
information and airplane transportation. I expect to characterize
flows in two different scales, one associated with long distance
travels and the other with daily commuting behavior. My ultimate goal
is to gain a better understanding of the dynamics of the underlying
mobility networks, in which nodes represent locations and links
represent travels. I will devise a unifying approach that could
directly be incorporated into current epidemic research.
175: Mark Dickison, Roni Parshani, Gene Stanley, Reuven Cohen and Shlomo Havlin. Dynamic networks and directed percolation    (abstract only)   information
Abstract. We introduce a model for dynamic networks, where the links or the strengths of the links change over time. We solve the model by mapping dynamic networks to the problem of directed percolation, where the direction corresponds to the evolution of the network in time. We show that the dynamic network undergoes a percolation phase transition at a critical concentration $p_c$, which decreases with the rate $r$ at which the network links are changed. The behavior near criticality is universal and independent of $r$. We find fundamental network laws are changed. (i) For Erd\H{o}s-R\'{e}nyi networks we find that the size of the giant component at criticality scales with the network size $N$ for all values of $r$, rather than as $N^{2/3}$. (ii) In the presence of a broad distribution of disorder, the optimal path length between two nodes in a dynamic network scales as $N^{1/2}$, compared to $N^{1/3}$ in a static network.
176: John Volpe. Sustainability and the myth of efficiency    (abstract only)   information
Abstract. Network theory is rapidly changing our understanding of ecological dynamics.  Recent advances suggest that contrary to most types of networks, indeterminacy among competing pathways and inefficiency of material transfer are key elements of stability and resilience in ecological systems. The implications of these findings are numerous and substantial.  Not least of these is the suggestion that conventional governance approaches to sustainability (via increasing resource use efficiency) are likely to fail. Conventional network analytical approaches are used to explore these results and their implications in the context of global resource sustainability.
177: andrea gabrielli and Guido Caldarelli. Invasion percolation on a tree and queueing models    (abstract only)   information
Abstract. We study the properties of the Barabási model of queuing [A.-L. Barábasi, Nature (London) 435, 207 (2005)] in the hypothesis that the number of tasks grows with time steadily. Our analytical approach is based on two ingredients. First we map exactly this model into an invasion percolation dynamics on a Cayley tree. Second we use the theory of biased random walks. In this way we obtain the following results: the stationary-state dynamics is a sequence of causally and geometrically connected bursts of execution activities with scale-invariant size distribution. We
recover the correct waiting-time distribution P(t)~t^{−3/2} at the stationary state as observed in different realistic data. Finally, we describe quantitatively the dynamics out of the stationary state quantifying the power-law slow approach to stationarity both in single dynamical realization and in average. These results can
be generalized to the case of a stochastic queue length in time non-decreasing in average and with limited fluctuations.
178: David Hachen and Omar Lizardo. Correlates of Reciprocity in a Large-Scale Communication Network:  A Weighted Edge Approach    (abstract only)   information
Abstract. Abstract for a contributed talk:

Network theory suggests that reciprocity is a key building block of human social networks.  However most empirical work on reciprocity relies on binary dyadic data and therefore has only been able to distinguish between mutual (reciprocal), asymmetric, and null dyads.  We extend prior work by developing a new measure of reciprocity based on edge weights such as dyadic interaction frequency.  This allows us to conceive of reciprocity as a continuous variable and investigate the distribution of reciprocity.  We examine the properties and correlates of our reciprocity measure using log data on the cellular telephone calls between 7 million users during a 16-day period.  Results indicate that non-reciprocity is more prevalent that past theories would lead us to expect.  The paper explores reasons for the observed reciprocity distribution with a specific focus on the affects that power law degree distributions and degree assortativity have on reciprocity.  We also test the long-standing idea that non-reciprocal relationships involve weak ties and examine whether Barabasi and Albert's (1998) "preferential attachment" mechanism, in which unpopular low-degree actors connect to more popular high degree "hubs," can account for observed non-reciprocity in networks.
179: Chang-Keun Yun, Naoki Masuda and Byungnam Kahng. Aggregation and condensation of dynamic clusters on complex networks    (abstract only)   information
Abstract. [Abstract for a poster]

Recently, dynamic problems on complex networks such as the Prisoner's Dilemma (PD) game have drawn considerable attention from diverse disciplines. The PD game is an evolution model describing mutual interactions among individuals in society. It was shown that cooperation is enhanced on random scale-free (SF) network compared with in the Euclidean space due to the presence of hubs. Hub and its surroundings in SF networks form a cluster of cooperators in the PD game, which is robust against the invasion by defectors, while such clusters do not form in the Euclidean space. In this paper, we show that when the network is a fractal that consists of local hubs and modular structure, local hubs play a role of the seed of cooperators and then isolated clusters of cooperators form around them, which are stable against the invasion of defectors. Due to the fluctuations arising in the PD game, the cluster size distribution of permanent cooperators exhibits a power law. More interestingly, as the fractal networks are changed to non-fractal networks by the addition of long-range edges to them, there occurs the percolation transition by the mechanism of cluster aggregations. We discuss the characteristics of this transition and its applications as well.
180: Arnab Chatterjee. Kinetic models for wealth exchange on directed networks    submission   information
Abstract. We propose some kinetic models of wealth exchange and investigate their behavior on directed networks though numerical simulations. We observe that network topology and directedness yields a variety of interesting features in these models. The nature of asset distribution in such directed networks show varied results, the degree of asset inequality increased with the degree of disorder in the graphs.
181: Marian Boguna. From lattices to small-worlds and back again or how we got rid of the Euclidean geometry to fall into the hyperbolic plane    submission   information
Abstract. Until very recently, statistical physicists used to work in euclidean lattices almost exclusively. This makes a lot of sense in systems which are naturally embedded in space and correlations between different parts of the system decreases with their distance. However, during the last decade, we have started to analyze a different class of systems for which distance considerations are (almost) absent and only the topological information of the interactions among the different elements matters. Examples range from social networks to communication networks like the Internet, or to metabolic and genetic regulatory networks in the cell. The lack of metric properties can be an advantage in some cases, for instance the small-world effect, but poses other problems as well. One of these concerns the communication protocols in the Internet --those allowing point to point communication among computers. Indeed, even if the small-world effect guarantees the existence of very short paths between any pair of nodes, finding such paths can be a difficult problem in {\it p2p} networks. In such cases, having metric properties associated to the pure graph topology can be very helpful.   
In this talk, we present a general class of models showing the same topological properties as real networks and which are, simultaneously, embedded in metric spaces. The model can be used to analyze the navigability properties of this class of networks and to infer the efficiency of real ones. Surprisingly, the natural extension of the model leads us towards hyperbolic geometries and Fermi statistics.
182: Thomas Fink. Exact solution of the critical Kauffman model with connectivity one    (abstract only)   information
Abstract. We give the exact solution for the number and size of attractors for boolean dynamics on a loop and multiple loops, which provides us with a solution for the critical Kauffman model with connectivity one. We introduce the notion of network resonance and characterize the dynamics in terms of Euler products.
183: Guido Caldarelli and Vinko Zlatic. Randomization Prcedure and Rich-club Coefficient    (abstract only)   information
Abstract. For many complex networks present in nature only a single instance, usually of large size, is available. Any measurement made on this single instance cannot be repeated on different realizations. In order to detect significant patterns in a real--world network it is therefore crucial to compare the measured results with a null model counterpart. Here we focus on dense and weighted networks, proposing a suitable null model and studying the behaviour of the degree correlations as measured by the rich-club coefficient. Our method solves an existing problem with the randomization of dense unweighted graphs, and at the same time represents a generalization of the rich--club coefficient to weighted networks which is complementary to other recently proposed ones.
184: Matti Peltomäki, Juha-Matti Koljonen, Mikko Alava and Olav Tirkkonen. SELF-ORGANIZED GRAPH COLORING    (abstract only)   information
Abstract. Graph coloring on various types on graphs is considered from the point of view
of designing self-organized algorithms to perform the coloring. Several new
ones are introduced and applied to various kinds of graphs including regular,
random planar, and random non-planar ones. The performance of the algorithms is
measured and compared to algorithms from the literature, the emphasis being on
the requirements of the algorithms, the convergence times to the complete
solution, and their reliability. The work has several applications on wireless
network management, for instance, and these are shortly discussed.
185: Stefan Wieland, Tomás Aquino and Ana Nunes. The Effect of SIS Dynamics with Contact Switching on Contact Network Topology    (abstract only)   information
Abstract. Disease dynamics on adaptive networks can significantly modify standard
model predictions (Gross et al. 2006, Shaw et al. 2008). The coupling of
disease and topology dynamics alters the underlying network and lets it
settle down to a characteristic state, irrespective of the starting
topology. Elaborating on the contact-switching SIS model of Gross et al.,
we describe infection-status clustering in the resulting steady-state
network. We discuss the derivation of the actual degree distribution
from the pair approximation equations using the generating function
186: Sebastian Ahnert, Thomas Fink and Andrei Zinovyev. Growth model for regulatory networks predicts lower bound on non-coding DNA in eukaryotes    (abstract only)   information
Abstract. Contributed talk:

Despite tremendous advances in the field of genomics, the amount and function of the large non-coding part of the genome in higher organisms remains poorly understood. We report an observation, made for 37 fully sequenced eukaryotic genomes, which indicates that eukaryotes require a certain minimum amount of non-coding DNA (ncDNA) [1]. This minimum increases quadratically with the amount of DNA located in exons. Based on a simple model of the growth of regulatory networks, we derive a theoretical prediction of this minimum of ncDNA and find it to be in excellent agreement with the data. The amount of additional ncDNA (in basepairs) which eukaryotes require obeys NDEF = 1/2 (NC / NP) (NC – NP), where NC is the amount of exonic DNA, and NP is a constant of about 10Mb. This value NDEF corresponds to a few percent of the genome in Homo sapiens and other mammals, and up to half the genome in simpler eukaryotes. Thus our findings confirm that eukaryotic life depends on a substantial fraction of ncDNA [2,3] and also make a prediction of the size of this fraction, which matches the data closely.

[1] S. E. Ahnert, T. M. A. Fink, A. Zinovyev, J. Theor. Biol. 252, 587 (2008).
[2] J. S. Mattick, Nat. Rev. Genet. 5, 316-323 (2004).
[3] R. J. Taft, M. Pheasant, J. S. Mattick, Bioessays 29, 288 (2007).
187: Tiziano Squartini and Diego Garlaschelli. Exact method for randomizing real networks    (abstract only)   information
Abstract. (Contributed Poster):

Any statement about the “complexity” of real networks relies on the comparison with a null model. Randomized graph ensembles that preserve only the local topological properties of a real network should always be used as the simplest null models, however their generation is still problematic. The existing approaches are either
statistically correct but only numerically accessible, time consuming and beyond analytic control, or analytically accessible but highly approximate, and not applicable to clustered, dense and finite networks. Here, we propose an exact and fast method that allows to obtain expectation values analytically and works for any unweighted or weighted network. Remarkably, after a fast preliminary parameter estimation, the time required to obtain exact averages of any property over the whole graph ensemble is the same as that required to compute the same property on the single original network, as it is not necessary to sample the configuration space explicitly. We show that, when applied to real networks, our method provides a novel and easy way to detect nontrivial patterns such as correlations, clustering and motifs.
188: Francesco Lombardo and Isabella Daidone. Museum network as a complex web    (abstract only)   information
Abstract. Complex network theory seems to offer a good representation of the fruition of "knowledge items" and of the development of the knowledge. The present work proposes a new way of analyzing the fruition of museums inspired by the powerful paradigmatic concept of scale-free networks. The museums are considered as the nodes of a network; the nature of the links is, though, not unique - this web could be considered as an overlap of different kinds of networks - and there is no chance to draw the exact structure of the net. Nevertheless, the degree distribution of this network can be indirectly estimated assuming that visitors' flows through each node is proportional to the number of links of that particular node. The Italian museum-network is here analyzed and the corresponding degree distribution is found to be fitted very well by a power-law function: this can be considered another clue that the way we use "knowledge items" is strictly related to a scale-free network representation.