Contributed Talks

NetSci07 will host a number of contributed talks both during the Workshop (May 20-21) and the Conference (May 22-25). Each talk is 15 minutes with 12 minutes presentation and 3 minutes reserved for questions and answers.

List of Talks

 Aral, Sinan (New York University and MIT) Tue., 11:40 - 11:55 m4a m4v Title #1: Network Structure & Information Advantage Abstract #1: We examine relationships between network structure, information structure, and individual performance in information intensive work. We build and validate an analytical model of information diversity, develop hypotheses linking two key aspects of network structure - size and diversity - to the distribution of novel information among actors, and test our theory using a ten month panel of email communication patterns, message content and performance data among employees of a medium sized executive recruiting firm. Our results indicate that: (1) the total amount of novel information and the diversity of information flowing to actors are increasing in their network size and network diversity. However, (2) the marginal increase in information diversity is decreasing in actors' network size, a result explained in part because (3) network diversity is increasing in network size, but with diminishing marginal returns. (4) Network diversity contributes to performance even when controlling for the positive performance effects of access to novel information, suggesting additional benefits to network diversity beyond those conferred through information advantage. Surprisingly, (5) traditional demographic and human capital variables have little effect on access to diverse information, highlighting the importance of network structure for information advantage. The methods and tools developed are replicable and can be readily applied to other settings in which email is widely used and available, opening a new frontier for the analysis of networks and information content. Back to Conference Program Aral, Sinan (New York University and MIT) Mon., 3:30 - 3:45 m4a m4v Title #2: Productivity Effects of Information Diffusion in Networks Abstract #2: We examine what drives the diffusion of different types of information through networks and the effects on performance. We characterize the social network of a medium sized executive recruiting firm using accounting data on project co-work relationships and ten months of email traffic. We identify two distinct types of information diffusing over this network -- event news' and discussion topics' -- by their usage characteristics, and observe several thousand diffusion processes of each type of information. We find the diffusion of news, characterized by a spike in communication and rapid, pervasive diffusion through the organization, is influenced by demographic and network factors but not by functional relationships (e.g. prior co-work, authority) or the strength of ties. In contrast, diffusion of discussion topics, which exhibit shallow diffusion characterized by back-and-forth' conversation, is heavily influenced by functional relationships and the strength of ties, as well as demographic and network factors. Discussion topics are more likely to diffuse vertically up and down the organizational hierarchy, across relationships with a prior working history, and across stronger ties, while news is more likely to diffuse laterally as well as vertically, and without regard to the strength or function of relationships. We also find access to information strongly predicts project completion and revenue generation. The effects are economically significant, with each additional "word see" correlated with about \$70 of additional revenue generated. Our findings provide some of the first evidence of the economic significance of information diffusion in networks. Back to Workshop Program Asztalos, Andrea (University of Notre Dame) Sun., 11:30 - 11:45 ppt pdf m4a Title: Discover a network by walking on it! Abstract: We study the exploration properties of a general class of random walks on arbitrary graphs. In particular, we refer to random walk processes in discrete space and time, where steps can take place only between nearest-neighbor sites. We derive general formulas for the rate at which nodes and edges of the underlying network are revealed as a function of time. These expressions are then specialized for a number of particular cases such as trees, complete graph, infinite and finite hypercubic lattices, random graphs and scale-free graphs. Back to Workshop Program Bansal, Shweta (University of Texas at Austin) Mon., 5:45 - 6:00 Title: Network frailty and the geometry of herd immunity Abstract: The spread of infectious disease through communities depends fundamentally on the underlying patterns of contacts between individuals. Generally, the more contacts one has, the more vulnerable one is to infection during an epidemic. Thus, outbreaks disproportionately impact the most highly connected demographics. Epidemics can then lead to sparser networks, through immunization or removal of individuals, which are more resistant to future transmission of a given disease. Using several classes of contact networks - Poisson, scale-free, and small-world - we characterize the structural evolution of a network due to an epidemic in terms of frailty - the degree to which highly connected individuals are more vulnerable to infection - and interference - the extent to which the epidemic cuts off connectivity among the susceptible population that remains following an epidemic. The evolution of the susceptible network over the course of an epidemic differs among classes of networks; frailty, relative to interference, accounts for an increasing component of network evolution on networks with greater variance in contacts. The result is that immunization due to prior epidemics can provide greater community protection than random vaccination on networks with heterogeneous contact patterns, while the reverse is true for highly structured populations. Back to Workshop Program Candia, Julian (University of Notre Dame) Sun., 2:15 - 2:30 m4a m4v Title: Irreversible Opinion Spreading on Complex Networks Abstract: We study the dynamical and critical behavior of a model for irreversible opinion spreading on small-world and scale-free networks by performing extensive Monte Carlo simulations. The opinion spreading is investigated by means of the magnetic Eden model, a nonequilibrium kinetic model for the growth of binary mixtures in contact with a thermal bath. Systems of finite size grow either ordered or disordered, depending on the temperature. These effective order-disorder phase transitions are extrapolated to the thermodynamic limit using standard finite-size scaling procedures. The existence of true critical transitions is found to be highly dependent on the topology of the complex network substrate: in the case of small-world networks, the system is critical for any positive shortcut density, but noncritical in the regular lattice limit; in the case of Barab´asi-Albert scale-free networks, the system is critical, but when considering uncorrelated scale-free networks, criticality depends on the degree exponent. Similarities and differences with results reported recently in the investigation of related equilibrium systems are also discussed. Back to Workshop Program Carter, Gregory W. (Institute for Systems Biology, Seattle) Sun., 3:15 - 3:30 ppt pdf m4a Title: Maximal Extraction of Biological Information from Genetic Interaction Data Abstract: The study of interactions between gene perturbations is a classical genetics technique to map biological pathways. Interactions between pairs of genes have historically been classified into different types with distinct biological interpretations. However, these classical analysis methods are not easily scaled to large, highthroughput data sets, where the growing volume of the data makes it difficult to preconceive the most informative classification of gene-gene relationships. Here we develop a method to extract the maximum amount of biological information from large data sets by optimizing the classification of interactions. The optimization is directed by computing the information content, or complexity, of the network based on the interrelationships between all network elements, placing each interaction in the context of the full data set. We have successfully validated this method on two examples from yeast by comparison with biological information extracted by annotated gene function. We suggest that our analysis represents a powerful and general approach to genetic interaction analysis, with particular potential in the study of mammalian systems in which interactions are complex and gene annotation data is sparse. Back to Workshop Program Christensen, Claire (Pennsylvania State University) Sun., 3:45 - 4:00 ppt pdf m4a Title: Disease Dynamics in a Dynamic Social Network Abstract: We outline a learning algorithm for the development of a realistic, evolving social network (a city) into which a disease is introduced. We compare the results of simulations in populations spanning two orders of magnitude to prevaccine era measles data for England and Wales and demonstrate that our simulations are able to capture the quantitative and qualitative features of epidemics in populations as small as 10,000 people. In addition, we show the utility of network simulation in concurrently probing contact network dynamics and disease dynamics, and we suggest that our suite of algorithms can be extended to the study of less well-documented diseases. Back to Workshop Program Clauset, Aaron (Santa Fe Institute) Tue., 11:25 - 11:40 m4a m4v Title: Hierarchical decomposition of complex networks Abstract: Hierarchical organization -- in which a system's components connect together into groups, and these groups into groups-of-groups, etc., at all scales of organization -- is believed to characterize the structure, and have strong implications for the function, of many real-world networks. In this talk, I will first present a general model of hierarchical structure, called the hierarchical random graph (HRG), and a technique for inferring hierarchy directly from data using maximum likelihood and Markov chain Monte Carlo sampling. I will then very briefly describe the results of applying this technique to several empirical networks, including a network of terrorist associations, a metabolic network and a food web. In particular, I will show that hierarchy can explain a wide variety of common structural features in complex networks -- such as the right-skewed degree distribution, non-trivial clustering coefficients, the small-world phenomenon, and both assortative and disassortative modular structure -- and that hierarchy is also a highly accurate predictor of missing or unobserved structure (a feature that may be particularly valuable for biological networks). Back to Conference Program Cosares, Steven (Hofstra University) Mon., 4:45 - 5:00 ppt pdf m4a m4v Title: Models for Hedging Disconnection Risk in a Network Plan Abstract: The task of determining a capacity expansion schedule for a facility comes with a variety of risks, particularly since it is difficult to accurately predict demand. If customers fail to arrive as forecast, capital spent on the expansion is wasted; if unexpected demands arise it may be necessary to incur an exorbitant expense to satisfy them in a timely manner. These risks are multiplied for a network where both the level and the location of new capacity must be determined. Further, networks are exposed to the risk incidents that might cut a link or disable a node, which would impact its ability to provide customers with connections. We describe how the financial (and sometimes social) implications of "disconnection risk" and "demand uncertainty risk" are important enough to require network planners to build in some hedges against them in their network designs. The terms "Survivability" and "Demand Flexibility" are used to describe network plans that have these hedges. We discuss methods for providing these hedges in a plan, evaluating their costs, and measuring their effectiveness. In some cases, it is possible to develop formulae that can used to define quantifiable constraints on the risks, so that reasonably hedged planning solutions might be generated by some mathematical programming model. Back to Workshop Program Csárdi, Gabor (KFKI Research Institute) Mon, 5:00 - 5:15 pdf m4a m4v Title: Quantifying the evolution of networks: the inverse problem Abstract: Many (complex or not) systems can be described as graphs with important parts or mod- ules as vertices and structural, functional or other relationships as edges. The evolution of a system means then the addition and/or deletion of vertices and/or edges to graph. In our model framework the evolution of this graph is described based on a so-called kernel- function, a function defining odds for the addition/deletion of individual vertices/edges. This function may depend on various structual and/or intrinsic properties of the vertices in the graph. We present how this model can be used to gain important knowledge about the network, via solving the inverse problem: determining the kernel function based on the network data. We also show how different models of this type can be compared as to which one is a better description of the underlying system. Some pieces of the methodology presented here have been published and presented earlier, see (Cs´ardi, 2006; Cs´ardi et al., 2007; Strandburg et al., 2006); the main novelty of this presentation is the definition of the error of a kernel function which makes possible to compare different descriptions of a network. Back to Workshop Program Diaz-Mejia, Juan Javier (Universidad National A. de Mexico) Fri., 11:25 - 11:40 ppt pdf m4a Title: A network perspective on the evolution of metabolism by gene duplication Abstract: Background: Gene duplication followed by divergence is one of the main sources of metabolic versatility. The patchwork and stepwise models of metabolic evolution help us to understand these processes, but their assumptions are relatively simplistic. We used a network-based approach to determine the influence of metabolic constraints on the retention of duplicated genes. Results: We detected duplicated genes by looking for enzymes sharing homologous domains and uncovered an increased retention of duplicates for enzymes catalyzing consecutive reactions, as illustrated by the ligases acting in the biosynthesis of peptidoglycan. As a consequence, metabolic networks show a high retention of duplicates within functional modules, and we found a preferential biochemical coupling of reactions that partially explains this bias. A similar situation was found in enzyme-enzyme interaction networks, but not in interaction networks of non-enzymatic proteins or gene transcriptional regulatory networks, suggesting that the retention of duplicates results from the biochemical rules governing substrate-enzyme-product relationships. We confirmed a high retention of duplicates between chemically similar reactions, as illustrated by fattyacid metabolism. The retention of duplicates between chemically dissimilar reactions is, however, also greater than expected by chance. Finally, we detected a significant retention of duplicates as groups, instead of single pairs. Conclusion: Our results indicate that in silico modeling of the origin and evolution of metabolism is improved by the inclusion of specific functional constraints, such as the preferential biochemical coupling of reactions. We suggest that the stepwise and patchwork models are not independent of each other: in fact, the network perspective enables us to reconcile and combine these models. Back to Conference Program DiBona, Pam (New England Aquarium) Wed., 5:00 - 5:15 m4a Title: Real World, Real Problem: Network Science to the Rescue? Abstract: New England and the Gulf of Maine region are densely populated with oceanoriented research and education institutions, organizations, and associations, each containing their own networks, collaborations, and partnerships. Several regional initiatives have attempted to link these networks using specific messages, goals, actions, or information, with limited success. We are investigating whether tools used in network science can help us cultivate a network of networks to provide effective and efficient communications and information sharing about ocean science education across the region. In this talk, we propose to present our case study for 5 minutes, and support discussion for the remaining 10 minutes of the scheduled time. Back to Workshop Program Dong, Wen (MIT Media Laboratory) Mon., 3:45 - 4:00 m4a m4v Title: Influence Modeling and Network Discovery Abstract: A time series of human behavior or group behavior often comprises samples of high dimensionality and complex probability distribution. The latent structure influence process models such a time series by simultaneously modeling the latent states of different parts of the samples, as well as the network structure among them. We demonstrate that an appropriate use of the network structure enables the influence modeling to achieve greater accuracy, efficiency, and robustness than the standard hidden Markov models, and to be applied to much larger applications. Back to Workshop Program Furukawazono, Tomoki (Keio University) Sun., 3:30 - 3:45 ppt pdf m4a Title: Historical Changes of Alliance Networks among Nations Abstract: The purpose of this paper is to show how the alliance networks among nations from 1816 to 2000. By our analysis, it was made clear that the alliance networks lead by the United States since World War II is a small-world network. Back to Workshop Program Gallos, Lazaros K. (City College of New York) Mon., 5:30 - 5:45 ppt m4a m4v Title: Degree correlations in complex networks Abstract: Correlations in the nodes connectivity have been identified as an important property of complex networks. While several empirical studies exist, there is no general theoretical analysis that can explain the largely varying behavior of real networks. Here, we use scaling theory to investigate these correlations and we are able to describe these properties using simple scaling exponents. This allows us to propose a classification of complex networks in terms of their correlation properties. The proposed classification sheds further insight on the structure of networks. For instance, we find that the degree correlations in the router level Internet are similar to those of a random network, while a smaller degree of hub correlations is found for the Internet at the Autonomous System level. Back to Workshop Program Getoor, Lise (University of Maryland) Thu., 11:25 - 11:40 ppt pdf m4a m4v Title: Entity Resolution in Networked Data Abstract: More and more, network analysis is being applied to large data collections, originally collected for other purposes, and potentially combined from multiple sources. Because of this, the data may be noisy, inaccurate and node references may be inexact (e.g., a 'John Smith' and 'J. Smith' may refer to the same underlying individual and two 'J. Smith's may refer to distinct individuals). Entity resolution in networked data is the problem of reconciling data references corresponding to the same real world entity. The goal is to reconstruct a cleaned' network that accurately captures the actual re- lationships among the true underlying entities. This is an important rst step in any network analysis process; mining an unresolved network will be ine cient and result in inac- curate conclusions. The novel aspect of our work is that we exploit both the attributes of the nodes and their relation- ships to aid in the resolution process. This results in a iter- ative algorithm that resolves references collectively, rather than on a pairwise basis. We demonstrate our algorithms on several data sets, including a large co-authorship network. Back to Conference Program Gonzalez, Marta C. (University of Notre Dame) Wed., 4:15 - 4:30 ppt pdf m4a Title: Study of human mobility patterns through the use of mobile phone communication Abstract: If you have a cell phone, your carrier knows always your whereabouts. In industrial countries with almost 100represent a huge opportunity to science, offering access to patterns of human mobility at a level and detail unimaginable before. Each cell phone communicates with the closest towers, which naturally partition a country into distinct geographic cells. Given that calls are recorded for billing purposes, one can reconstruct the movement of each mobile phone user. Using a data set over a million of individual displacements, we quantify the main features of human daily travels witihin a country. First, the distribution of traveling distance decays as a power law. Second, individuals move in confined areas with a characteristic length or radius of gyration, with the distribution of this radius being heavy tailed. We show that human traveling behavior can be described mathematically on many spatiotemporal scales to a surprising accuracy by a sort of centrally biased random walk. Back to Conference Program Gulbahce, Natali (Los Alamos National Laboratory) Wed., 11:25 - 11:40 m4a Title: Exploring the metabolic network for improved functionality Abstract: Constraint-based modeling techniques have proven to be useful in predicting the metabolic behavior of single-celled organisms after a severe mutation. Two such methods, Minimization of Metabolic Adjustment (MOMA) and Flux Balance analysis (FBA) can be used to predict the growth rate of a cell right after a mutation and after adaptative evolution, respectively. Recently we have shown that by rerouting the fluxes of the underlying metabolic network, some of the effects of a mutation can be circumvented. In this talk, I will describe the details of this procedure and present data for several single-celled organisms. Back to Conference Program Hidalgo R., Cesar A. (University of Notre Dame) Wed., 11:40 - 11:55 m4a Title: The Product Space Conditions the Development of Nations Abstract: Economies grow by upgrading the type of products they produce and export. The technology, capital, institutions and skills needed to make these products are more easily adapted to produce some products than others. We study the network of relatedness between products, or 'product space', finding that most upscale products are located in a densely connected core while lower income products occupy a less connected periphery. We show that countries tend to move to goods close to those they are currently specialized in, allowing those located in more connected parts of the product space to upgrade their exports basket more quickly. Most countries can reach the core only if they "jump" over empirically infrequent distances in the product space. This may help explain why poor countries have trouble developing more competitive exports, failing to converge to the income levels of rich countries. Back to Conference Program Hook, Peter A. (Indiana University) Tue., 4:30 - 4:45 ppt m4a Title: Network Derived Domain Maps of the Work of the United States Supreme Court: 50 years of Co-Voting Data and a Case Study on Abortion Abstract: The recent abortion case decided by the United States Supreme Court has once again brought abortion and the importance of the Supreme Court to the forefront of the American public's attention. Domain maps created by network science techniques and other spatial layout mechanisms such as Multi-Dimensional Scaling (MDS) have much to contribute towards teaching the public about the dynamic interaction of case law precedent and the changing membership of the Supreme Court. This work utilizes a 50 year dataset of the network of co-voting relationships among the Justices of the Supreme Court, as well as West Topic assignments, citation interlinkages, and citation counts relevant to abortion cases to illustrate the history of abortion law in the United States Supreme Court. Back to Conference Program Huang, Weixia (Indiana University) Wed., 4:00 - 4:15 pdf m4a Title: Network Workbench – Using Service-Oriented Architecture and Component-Based Development to Build a Toolkit for Network Scientists Abstract: There is an increasing requirement on interdisciplinary research and the collaborations of researchers from different research communities. An example is the emerging new field -- network science[18] aiming at the study of small, medium, and large-scale network datasets collected in social and behavioral science, physics, biology, and other disciplines. At an increasing rate, the scientists that invent and implement new algorithms are not computer scientists. Yet, the algorithms they invent and implement are useful within and outside of their own disciplines. The question then becomes: How can those hundreds and thousands of individual algorithms that are programmed in different languages for different purposes and data formats most effectively be made available to nonprogrammer users spread out across multiple disciplines? This paper introduces the Network Workbench (NWB) tool with a service-oriented architecture, which supports the plug and play of algorithms and datasets, and the handling of diverse data formats via the data conversion service. We describe the core of the NWB tool – Cyberinfrastructure Shell (CIShell) framework, and the key features and usage of the tool. We conclude with an outlook of planned work. Back to Conference Program Iba, Takashi (Keio University) Sun., 2:45 - 3:00 ppt pdf m4a Title: Iterated prisoner's dilemma on alliance networks Abstract: The objective of this paper is to clarify the characteristics of the alliance network that Japan belonged to after the World War II. On that alliance network, iterated prisoner's dilemma game will be played. Back to Workshop Program Kitsak, Maksim (Boston University) Mon., 5:15 - 5:30 ppt pdf m4a m4v Title: Transport Properties of Fractal and Non-Fractal Scale-Free Networks Abstract: We study transport related properties of fractal and non-fractal models and real scale-free networks. We show that the correlation between degree and centrality betweenness C of nodes is much weaker in fractal networks compared to non-fractal networks. In order to characterize and quantify the overall centrality betweenness - degree correlation we propose a correlation dispersion coefficient R, which can distinguish between fractal and non-fractal networks. The centrality betweenness of nodes of both fractal and non-fractal networks exhibits a power-law distribution P(C) ~ C^{-d}. We suggest that for non-fractal scale-free networks d = 2, and for fractal scale-free networks d = 2 - 1/dB, where dB is the fractal dimension of the network. A crossover phenomenon from fractal to non-fractal networks occurs upon adding random edges to a fractal network. We show that the crossover length l*, separating fractal (l < l*) and non-fractal (l > l*) regimes, scales with dimension dB of the network as p^{-1/dB}, where p is the density of random edges added to the network. We test these new results by explicit calculations on four real networks: pharmaceutical firms (N = 6776), yeast (N = 1458), WWW (N = 2526), and the Internet network at AS level (N = 20566), where N is the number of nodes in the largest connected component of a network. (Kitsak et al., Phys. Rev. E. (in press) (2007), physics/0702001) Back to Workshop Program Lee, Deok-Sun (University of Notre Dame) Sun., 4:30 - 4:45 pdf m4a m4v Title: Metabolomic links of human diseases Abstract: Breakdown of a part of metabolism can relate to disorders in diverse stages of their developments. Here we map inherited disorders, with which a gene mutation is associated, to segments of the metabolic pathways on a global scale utilizing the catalysis relationship between metabolic reactions and enzymes and the disease-gene association. By segment, we mean a set of consecutive metabolic reactions converting or producing the same compound, being a functional unit as demonstrated by the genes coding their enzymes highly co-expressed. From this mapping, we can construct a human disease network where nodes are diseases and two diseases are connected if they are associated with the same segment of the metabolic pathways. We will discuss the topology of this disease network. Connected diseases in the network are expected to co-occur in a patient and we test this hypothesis against the disease data of 13 million patients during a 4-year period. Our analysis shows that the tendency of co-occurrence is much higher for connected diseases than that of disconnected ones. We present examples of connected diseases with high co-occurrence and their associated metabolic pathways. Back to Workshop Program Lietz, Haiko (Columbia University) Sun., 12:00 - 12:15 ppt pdf m4a m4v Title: The Fractal Polity: Why Schröder Failed at the Second Term Abstract: In 2005 the German government failed in the middle of its widely opposed reform of the welfare state. Why did it fail? Sometimes, or usually, social order is too strong, structure too solid, as to allow fresh action over blocking action. This is certainly true for German politics. Because outcome is related to social structure, it must first be understood where social order comes from. Emergence and self-similarity are the keys. The policy networks literature contrasts hierarchical with heterarchical forms of governance. Relying on Harrison White's (Forthcoming-b) updated structural theory of social action and complex systems theory, this paper theorizes that hierarchy and heterarchy are non-exclusive scale-free foci of organization that have structure emerge on different levels. Understanding structure as the result of self-similar enactment of styles that shun mismatch by nature, fresh action is conceptualized as the fruitful confrontation of mismatch. The sufficient condition for successful policy-making is the existence of a structure for the production of policy decisions, formal modes of exchange. The necessary condition is the existence of a structure for the mediation of policy issues, heterarchical modes of exchange that self-organize diversity. The hypothesis is that the necessary condition is not fulfilled in policy domains related to the reform of the welfare state. This is tested using data of affiliations of German deputies with public, semi-private, and private organizations in the networked polity. The data enables the analysis of directed intra-parliamentary informal communication networks. I first show that these networks have complex systems properties. Operationalizing heterarchy by reciprocity and Krackhardt's graph theoretical dimensions (Krackhardt 1994, Krackhardt & Stern 1988) I show that the networks are meaningful by demonstrating that their properties differ according to policy domains and according to size. Finally, I show that the structures of two policy domains that were related to the failed reform project did not have the heterarchical properties that can be found in two different policy domains that produced successful output. Back to Workshop Program Lin, Ching-Yung (IBM T. J. Watson Research Center) Fri., 10:50 - 11:25 ppt m4a Title: Information Flow Prediction by Modeling Dynamic Probabilistic Social Network Abstract: We propose a novel Behavioral Information Flow (BIF) model which can be used to predict how information is propagated through a complex social network. We consider both dynamic and probabilistic characteristics of human behavior in receiving and redirecting information. Information can be duplicated without any distortion and send to as many people as the user has in his social network connections. In a sense, this is similar to the epidemic or computer virus propagation. However, previous studies were mostly focused on the overall societal properties. Seldom did previous studies focus on the factors of both personal behavior and network topology. Neither did we see the changing properties of human behavior and probabilistic nature being considered. In this paper, we first propose to model a Dynamic Probabilistic Complex Network as a combination of the state probabilities of user nodes and connection edges and two transition functions that are dependent on the network topology and user properties. Then, we propose to model user transitions as Susceptible - Active - Informed (SAI) states and edge transitions as a Markov Model with Susceptible - Dormant - Active - Removed (SDAR) stages. Based on these modeling methods, we can then predict information flows in a social network. We have applied this model for the applications of finding important people. Our preliminary experimental results have demonstrated the effectiveness of the proposed models. Back to Conference Program López, Eduardo (Los Alamos National Laboratory) Thu., 11:40 - 11:55 ppt pdf m4a m4v Title: Limited path percolation in complex networks Abstract: We study the stability of network communication after removal of q = 1-p links under the assumption that communication is effective only if the shortest path between nodes i and j after removal is shorter than a l_{ij} (a>=1) where l_{ij} is the shortest path before removal. For a large class of networks, we find a new percolation transition at p_c = (\kappa_{o} - 1)^{(1 - a)/a}, where \kappa_o \equiv / and k is the node degree. Below p_c, only a fraction N^{\delta} of the network nodes can communicate, where \delta \equiv a(1 - |log p |/log(\kappa_o - 1)) < 1, while above p_c, order N nodes can communicate within the limited path length a l_{ij} . Our analytical results are supported by simulations on Erdös - Rényi and scale-free network models. We expect our results to influence the design of networks, routing algorithms, and immunization strategies, where short paths are most relevant. Back to Conference Program Lu, Qiming (Rensselaer Polytechnic Institute) Sun., 2:00 - 2:15 ppt pdf m4a m4v Title: Naming Game in Social Networks Abstract: We investigate a simple agent-based model, the Naming Game, on both prototypical complex networks and real social networks. The Naming Game is a minimal model with local communications capturing the spontaneous emergence of shared classification schemes (dictionaries) in a population of autonomous semiotic agents. Here we apply the Naming Game to empirical high-school friendship networks. The agreement process exhibits fundamental scaling features in the course of reaching consensus, and long-living metastable (multi-domain) configurations in the late stage of agreement processes. The latter feature is due to the presence of strong community structures in real-life social networks, and in turn, the model can be used to detect community structures in complex social networks . Back to Workshop Program Ma, Xiulian (University of Utah) Sun., 2:30 - 2:45 ppt pdf m4a m4v Title: Chinese City System Formation and Globalization Abstract: Theories predict that the Chinese city system in the reform era (starting from the late 1970s) would increasingly conform to a log-normal (or rank-size rule) distribution due to growing market force. And as the country becomes more involved in global process, the Chinese city system would also become more primate, and certain structural disarticulation would grow between the global cities or primate cities and the rest of the city system. Employing both the conventional population ranking method and network analysis, the paper examined the Chinese city system change with respect to these predictions. In terms of network analysis, it uses air passenger flows among 43 largest Chinese cities as a basis for estimates of network properties, such as the global centrality and network position. It also employs a longitudinal network to examine the effect of globalization on the city network change. The research found that both methods provide little support for the theoretical predictions. The paper argues that such anomaly is because the transitional Chinese state instead of market or globalization has played a much more significant role restructuring Chinese city system. The state has reshaped the city system through erecting against the development of largest cities, managing economic openness, and state policies that favor political decentralization in which the local governments have wielded more power. Back to Workshop Program Nepusz, Tamas (Budapest Univ. of Techn. and Econ.) Sun., 11:45 - 12:00 pdf m4a m4v Title: Fuzzy Communities and the Concept of Bridgeness in Social Networks Abstract: Recent research revealed that the graph models of many realworld phenomena exhibit an overlapping community structure which is hard to grasp with the classical graph clustering methods where every vertex of the graph belongs to exactly one community. This is specifically true for social networks where it is not uncommon that a couple individuals in the network are indeed "bridges" between communities. On the other hand, fuzzy clustering data mining methods (e.g. fuzzy cmeans ) have already been successfully applied on non-graph-like datasets. In this paper, we will present a method which introduces the concept of fuzziness in community detection, so a vertex of the graph can belong to multiple communities at the same time with some degree of membership as long as the degrees of memberships add up to 1. This extension will also allow us to detect the above mentioned individuals who act as "bridges" between communities. An application of the method on the social network of the faculty staff of a UK university will also be presented. Back to Workshop Program Oikonomou, Panos (University of Chicago) Sun., 4:15 - 4:30 ppt pdf m4a m4v Title: Evolvable by design Abstract: As the architecture of a growing number of networks is unveiled, their intricate design raises a general question: Is there a specific network topology that confers some kind of evolutionary advantage? We can demonstrate how the architecture of such systems governs their ability to evolve. We use boolean threshold components to model network dynamics. We compare two distinct designs: homogeneous networks which are randomly structured, and heterogeneous scale-free networks for which the distribution of connections follows a power law. Our simulations show that populations containing scale-free networks can easily produce a number of functional variations which allow each population to evolve rapidly and smoothly towards a target function. By contrast, equivalent random networks evolve slowly, through a succession of rare advantageous random mutations. We examine these results in terms of the dynamical properties and the information flow in such networks. Back to Workshop Program Pacheco, Jorge M. (Universidade de Lisboa) Fri., 10:15 - 10:50 pdf m4a Title: Evolutionary dynamics on networks, with broken symmetry between interaction and replacement Abstract: We study evolutionary dynamics in a population whose structure is defined in terms of two networks: the interaction network determines who plays with whom in an evolutionary game; the replacement network specifies the structure of evolutionary competition. We investigate the evolution of cooperation modeled in terms of social dilemmas associated with symmetric 2 x 2 games played in finite populations and show that it is always harder for cooperators to evolve whenever the interaction network and the replacement network do not coincide. In the thermodynamic limit, we show that the dynamics taking place on both networks is given by a replicator equation with a rescaled payoff matrix in a rescaled time, a result which is valid for general symmetric m x m games with m >= 2. Our analytical results are obtained using the pair-approximation method in the limit of weak selection, whose validity is checked by exact computer simulations. Back to Conference Program Park, Han Woo (YeungNam University) Wed., 4:45 - 5:00 ppt pdf m4a Title: A longitudinal analysis of blog linkages among South Korean politicians Abstract: This paper, which examines trends in blog linkages among political actors in Korea, will provide a longitudinal analysis of blog linkages, in order to assess whether there are any long term implications of new media technologies in Korean society and politics. The data were gathered from the blogs of Korea’s National Assemblymen for 2005 and 2006. The results indicated that there is an increased use of blogs among National Assembly members. However, it seems that over time, the network has become sparser, less integrated, and decentralized. Back to Conference Program Perer, Adam (University of Maryland) Sun., 3:00 - 3:15 pdf m4a m4v Title: Balancing Systematic and Flexible Exploration of Social Networks Abstract: Social network analysis (SNA) has emerged as a powerful method for understanding the importance of relationships in networks. However, interactive exploration of networks is currently challenging because: (1) it is difficult to find patterns and comprehend the structure of networks with many nodes and links, and (2) current systems are often a medley of statistical methods and overwhelming visual output which leaves many analysts uncertain about how to explore in an orderly manner. This results in exploration that is largely opportunistic. Our contributions are techniques to help structural analysts understand social networks more effectively. We present SocialAction, a system that uses attribute ranking and coordinated views to help users systematically examine numerous SNA measures. Users can (1) flexibly iterate through visualizations of measures to gain an overview, filter nodes, and find outliers, (2) aggregate networks using link structure, find cohesive subgroups, and focus on communities of interest, and (3) untangle networks by viewing different link types separately, or find patterns across different link types using a matrix overview. For each operation, a stable node layout is maintained in the network visualization so users can make comparisons. SocialAction offers analysts a strategy beyond opportunism, as it provides systematic, yet flexible, techniques for exploring social networks. Back to Workshop Program Rozenfeld, Hernan D. (Clarkson University) Mon., 3:00 - 3:15 pdf m4a m4v Title: Percolation in Hierarchical Scale-Free Nets Abstract: We study the percolation phase transition in hierarchical scale-free nets. Depending on the method of construction, the nets can be fractal or small-world (the diameter grows either algebraically or log- arithmically with the net size), assortative or disassortative (a measure of the tendency of like-degree nodes to be connected to one another), or possess various degrees of clustering. The percolation phase transition can be analyzed exactly in all these cases, due to the self-similar structure of the hi- erarchical nets. We find different types of criticality, illustrating the crucial effect of other structural properties besides the scale-free degree distribution of the nets. Back to Workshop Program Santos, Francisco C. (Universite Libre de Bruxelles) Thu., 4:00 - 4:15 ppt pdf m4a m4v Title: Cooperation prevails when individuals adjust their social ties Abstract: In social networks, some individuals interact more frequently and with more people than others. In this context, one may wonder: under which conditions are social beings willing to be cooperative? Current models proposed in the context of evolutionary game theory cannot explain cooperation in communities with a high average number of social ties. We show that when individuals are allowed to simultaneously alter their behaviour and their social connections, cooperation may prevail. Moreover, the emerging social networks exhibit an overall heterogeneity that matches the diversity of patterns found in recent studies of social networks. We also conclude that the more individuals interact, the more they must be able to promptly adjust their partnerships for cooperation to thrive. Consequently, to understand the occurrence of cooperative behaviour in realistic settings, the interplay between the evolution of the complex network of interactions and the evolution of strategies should be taken into account. Back to Conference Program Sayama, Hiroki (State University of New York) Mon., 4:15 - 4:30 ppt pdf m4a m4v Title: Unifying Dynamical Systems and Complex Networks Theories Abstract: A variety of modeling frameworks have been proposed and utilized in complex systems studies, including dynamical systems models that describe state transitions within a system of fixed topology, and complex networks models that describe topological transformations of a network with little attention paid to dynamical state changes. However, many real-world complex networks exhibit both of these two dynamics simultaneously, which are often deeply intertwined with each other. To unify the existing dynamical systems and complex networks theories, here we propose a novel modeling framework, named “generative network automata (GNA)”, that can uniformly describe both state transitions and autonomous topology transformations of complex dynamical networks. The evolution of GNA is defined as a generative process realized by repetitive local subnetwork rewritings. This paper presents the formal definition of GNA and demonstrates via computational simulations its generality to represent other complex dynamical network models. Back to Workshop Program Sevim, Volkan (Florida State University) Sun., 4:45 - 5:00 pdf m4a m4v Title: Does Evolution of Robustness Change the Dynamic Properties of Genetic Regulatory Networks? Abstract: Gene networks are extremely robust against genetic perturbations [1, 2]. For example, systematic gene knock-out studies on yeast showed that almost 40% of genes on chromosome V have no detectable e ects on several indicators like cell division rate [3]. Similar studies on other organisms agree with these results [1, 2]. It is also known that species do not have much phenotypic variation, although they experience a wide range of environmental and genetic perturbations. This resilience makes one wonder about the origins, evolutionary consequences, and mechanistic causes of genetic robustness. It has been proposed that genetic robustness evolved through stabilizing selection for a phenotypic optimum. Wagner showed that this in fact could be true by modeling a developmental process within an evolutionary scenario, in which the genetic interaction sequence represents organismal development, and the equilibrium con guration of the gene network represents the phenotype [4]. His results show that the genetic robustness of a population of model genetic regulatory networks can increase through stabilizing selection for a particular equilibrium con- guration (phenotype) of each network. We investigate the e ects of the evolution of genetic robustness on the dynamics of gene regulatory networks using the model mentioned above. In particular, we want to answer the question whether such selection could result in a reorganization of the state space of the system. Put di erently, we investigate whether the evolution process moves the system to a di erent point in the phase diagram, perhaps to another phase (chaotic or ordered) [5]. We present some preliminary results, including that this network model is always chaotic. Also, the evolutionary process that improves the genetic robustness of such networks seems to have a small e ect on their dynamical properties: the system moves slightly toward the more ordered part of the phase diagram after evolution. However, it remains chaotic.

Last Updated April 9th, 2007 | Site Design by Elisha Hardy