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.
<

Back to Workshop Program

Sreenivasan, Sameet (University of Notre Dame) Thu., 4:30 - 4:45 m4a m4v

Title: 
Structural Communication Bottlenecks in Networks
Abstract: 
We consider the effect of network topology on the efficiency of packet routing in the case of static routing protocols, where a unique route is used for communication between a given pair of nodes. We quantify the optimality of packet routing by c, the rate of packet insertion beyond which congestion and queue growth occurs. In particular, our analysis focuses on the scaling of c with the network size N. We show that for any network, there exists an absolute upper bound to this scaling, and that this upper bound can be expressed in terms of vertex separators, irrespective of the static routing protocol used. We then derive an estimate to this upper bound for scale-free networks, and introduce a static routing protocol, the "hub avoidance protocol" which, for large packet insertion rates, is superior to the shortest path routing protocol.

Back to Conference Program

Sundararajan, Arun (New York University) Mon., 4:30 - 4:45 pdf m4a m4v

Title: 
Network Structure and the Long Tail of Electronic Commerce
Abstract: 
We report on a research project that studies how network structures affect demand in electronic commerce, using daily data about the graph structure of Amazon.com’s co-purchase network for over 250,000 products. We describe how the presence of such network structures alters demand patterns by changing the distribution of traffic between ecommerce web pages. When this traffic distribution generated by the presence of the network is less skewed than the intrinsic or "real world" traffic distribution, such network structures will even out demand across products, leading to a demand distribution with a longer tail. We estimate an econometric model to validate this theory, and report on preliminary confirmation by contrasting the demand distributions of products within over 200 distinct categories on Amazon.com. We measure the overall extent to which a product influences the network by adapting Google’s PageRank algorithm, applying it to a weighted composite of graphs over four distinct 7-day periods, and we characterize the demand distribution of each category using its Gini coefficient. Our results establish that categories whose products are influenced more by the network structure have significantly flatter demand distributions, which provides an additional explanation for the widely documented phenomenon of the long tail of ecommerce demand.

Back to Workshop Program

Thadakamalla, Hari P. (Pennsylvania State University) Tue., 4:45 - 5:00

Title: 
Decentralized search in spatial scale-free networks
Abstract: 
In this paper, we present the results obtained recently on decentralized search problem in a family of parameterized spatial network model, heterogeneous in node degree. We investigate several decentralized search algorithms and illustrate that some of these algorithms exploit the heterogeneity in the network to find paths as small as the shortest paths found by using global information. We demonstrate that this spatial network model belongs to a class of searchable networks for a wide range of parameter space. Further, we test these algorithms in the U.S. airline network and demonstrate that searchability is a generic property of the U.S. airline network.

Back to Conference Program

Uchida, Makoto (University of Tokyo) Sun., 5:00 - 5:15 pdf m4a m4v

Title: 
Identifying the Large-Scale Structure of Blogosphere
Abstract: 
We analyze a topological structure of a network formed according to the entries and track-backs in the blogosphere. The analysis is based on community ex-traction and network visualization. It is shown that the blogosphere has a globally sparse, but locally dense structure. The entries in a community yield the dense structure and the trackbacks interconnect communities are sparse. The visualized results show "sparkling-firework-like" patterns. And then, we try to character-ize the communities using a TF-IDF technique. It is found that specific topics are discussed in each com-munity. These results would help us to identify the community in which some specific topics discussed, and to detect trends in the blogosphere.

Back to Workshop Program

Waber, N. Benjamin (MIT Medial Laboratory) Mon., 3:15 - 3:30 ppt pdf m4a m4v

Title: 
Organizational Engineering using Sociometric Badges
Abstract: 
We show how a wearable computing research platform for measuring and analyzing human behavior can be used to understand social systems. Using a wearable sociometric badge capable of automatically measuring the amount of face-to-face interaction, physical proximity to other people, and relative location, we are able to construct a dynamic view of an organization’s social network by viewing interactions as links between actors. Combining this with email data, where e-mail exchanges indicate a social tie, we are able to form a robust view of the social network, using proximity information to remove spurious e-mail exchanges. We attempt to use on-body sensors in large groups of people for extended periods of time in naturalistic settings for the purpose of identifying, measuring, and quantifying social interactions, information flow, and organizational dynamics. We discuss how this system can lead to an automatic intervention system that could optimize the social network in real time by facilitating the addition and removal of links based on objective metrics in a socially natural way. We deployed this research platform in a group of 22 employees working in a real organization over a period of one month, and we found that betweenness in the combined social network had a high negative correlation of r = -0.49 (p < 0.05) with perceived group interaction quality.

Back to Workshop Program

Webb, Matthew (US Military Academy Network Science Center) Sun., 5:15 - 5:30 ppt m4a m4v

Title: 
Detecting Changes in Social Networks Using Statistical Process Control
Abstract: 

Back to Workshop Program

Xie, Le (Carnegie Mellon University) Sun., 11:15 - 11:30 ppt pdf m4a m4v

Title: 
Dynamic Aggregation for Monitoring and Decision Making in Electric Power Systems
Abstract: 
The transmission network for delivering electrical power in North America is one of the most complex largescale man-made systems. As the system is operated under increasing level of stress, near-real time monitoring and decisionmaking tools are necessary for the system to perform gracefully under both normal and abnormal conditions. Two questions are addressed in this paper, namely ?how to decompose the power network? and ?how to monitor the system from the decomposed subsystems.? More specically, a dynamic aggregation method is proposed to monitor voltage stability of electric power grids in a decentralized way. Such method potentially forms a basis for designing guaranteed performance of electric power grids.

Back to Workshop Program

Xu, Xiaowei (University of Arkansas at Little Rock) Thu., 4:15 - 4:30 pdf m4a

Title: 
Finding Structure-Connected Clusters in Networks
Abstract: 
Networks are ubiquitous, and as we become aware of them we find that they contain much valuable information. The World Wide Web, social networks and metabolic networks are examples of networks that are now the subject of study. Network clustering (or graph partitioning) is the discovery of underlying clusters of related vertices in networks. But beyond organizing vertices into clusters of peers is the question of what role each vertex play in the network. This paper presents some new ways of uncovering underlying structures, including the roles that vertices play in the network. We begin by defining a property we call structural similarity. We then define a structure-connected cluster (SCC) as a collection of vertices they have strong structural similarity. Finally, we propose an algorithm that only finds SCCs that represent groups of peers in networks, but also identify vertices that play special roles such hubs that bridge clusters and outsiders that are marginally connected to clusters. Identifying vertex roles is useful for applications such as viral marketing and epidemiology. For example, hubs are responsible for spreading ideas or disease. In contrast, outsiders have little or no influence, and may be isolated as noise in the data. We evaluate the performance of our algorithm using various measures of structural similarities. An empirical evaluation of the algorithm using both synthetic and real datasets demonstrates superior performance over other methods such as modularity-based algorithms.

Back to Conference Program

Yildirim, Muhammed (Dana-Farber Cancer Institute) Wed., 4:30 - 4:45 ppt pdf m4a

Title: 
Drug Target Network
Abstract: 
The global set of relationships between protein targets of all drugs and all disease gene products in the human protein-protein interaction or "interactome" network remains uncharacterized. We built a bipartite graph composed of FDA-approved drugs and proteins linked by drug-target binary associations. The resulting network connects most drugs into a highly interlinked giant component, with strong local clustering of drugs of similar types according to anatomical therapeutic chemical classification. Topological analyses of this network quantitatively showed an over-abundance of "follow-on" drugs, i.e. drugs that target already targeted proteins. By including drugs currently under investigation, we identified a trend towards more functionally diverse targets improving polypharmacology. To analyze the relationships between drug targets and disease gene products, the shortest distance between both sets of proteins was measured in current models of the human interactome network. Significant differences in distance were found between etiological and palliative drugs. Lastly, a recent trend towards more rational drug design was observed.

Back to Conference Program

Zhang, Haizheng (Pennsylvania State University) Thu., 4:45 - 5:00 m4a

Title: 
An LDA-based Probabilistic Community Structure Discovery Approach for Large-Scale Social
Abstract: 
Community discovery has drawn significant research interests among researchers from many disciplines for its increasing application in multiple, disparate areas, including computer science, biology, social science and so on. This paper describes an LDA(latent Dirichlet Allocation)-based hierarchical Bayesian algorithm, namely SSN-LDA(Simple Social Network LDA). In SSN-LDA, communities are modeled as latent variables in the graphical model and de ned as distributions over the social actor space. The advantage of SSN-LDA is that it only requires topological information as input. This model is evaluated on two research collaborative networks:CiteSeer and NanoSCI. The experimental results demonstrate that this approach is promising for discovering community structures in large-scale networks.

Back to Conference Program

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