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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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).
|
|
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.
|
|
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.
|
|
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. |
|
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.
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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)
|
|
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.
|
|
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.
|
|
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.
|
|
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
|
|
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 .
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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. |
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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: |
|
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.
|
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.
|
|
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.
|
|
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.
|
Last Updated April 9th, 2007 | Site Design by Elisha Hardy