Bulletin of the American Physical Society
2005 APS March Meeting
Monday–Friday, March 21–25, 2005; Los Angeles, CA
Session A24: Focus Session: Structure, Dynamics and Resilience of Complex Networks |
Hide Abstracts |
Sponsoring Units: GSNP Chair: Alessandro Vespignani, Indiana University Room: LACC 411 |
Monday, March 21, 2005 8:00AM - 8:12AM |
A24.00001: An information theoretic derivation of spectral graph partitioning Manuel Middendorf, Etay Ziv, Chris Wiggins At the APS meeting in 2004, we introduced an information-theoretic algorithm called the ``network information bottleneck" (NIB) for clustering nodes of a network into modules (cf. arxiv.org/q-bio/0411033). Numerical experiments show that, although the modules are found by minimizing a free energy with no references to normalized edge-cuts or numbers of edges between modules, the resulting partitions are both information-modular and edge-modular (exhibiting low normalized edge-cuts). Moreover, the resulting partioning algorithm is competitive both in accuracy and efficiency with methods popular in the physics community. These numerical results along with asymptotic equivalence between the information-optimal and edge-optimal partitionings are presented. [Preview Abstract] |
Monday, March 21, 2005 8:12AM - 8:24AM |
A24.00002: Traceroute-like exploration of unknown networks: a statistical analysis Alain Barrat, Luca Dall'Asta, Ignacio Alvarez-Hamelin, Alexei Vazquez, Alessandro Vespignani Mapping the Internet generally consists in sampling the network from a limited set of sources by using {\tt traceroute}-like probes. This methodology has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sampled graph which sharply differ from the original ones. Here we explore these biases and provide a statistical analysis of their origin. We derive a mean-field analytical approximation for the probability of edge and vertex detection that exploits the role of the number of sources and targets and allows us to relate the global topological properties of the underlying network with the statistical accuracy of the sampled graph. In particular we show that shortest path routed sampling allows a clear characterization of underlying graphs with scale-free topology. We complement the analytical discussion with a throughout numerical investigation of simulated mapping strategies in different network models. [Preview Abstract] |
Monday, March 21, 2005 8:24AM - 8:36AM |
A24.00003: Effects of Community Structure on Search and Ranking in Information Networks Huafeng Xie, Koon-Kiu Yan, Sergei Maslov The World-Wide Web (WWW) is characterized by a strong community structure in which communities of webpages (e.g. those sharing a common keyword) are densely interconnected by hyperlinks. We study how such network architecture affects the average Google ranking of individual webpages in the community. It is shown that the Google rank of community webpages could either increase or decrease with the density of inter-community links depending on the exact balance between average in- and out-degrees in the community. The magnitude of this effect is described by a simple analytical formula and subsequently verified by numerical simulations of random scale-free networks with a desired level of the community structure. A new algorithm allowing for generation of such networks is proposed and studied. The number of inter-community links in such networks is controlled by a temperature-like parameter with the strongest community structure realized in ``low-temperature'' networks. [Preview Abstract] |
Monday, March 21, 2005 8:36AM - 9:12AM |
A24.00004: Community discovery and information flow in networks Invited Speaker: The dynamics of information within social groups is relevant to issues of productivity, innovation and the sorting out of useful ideas from the general chatter of a community. How information spreads and is aggregated determines the speed with which individuals and organizations can act and plan their future activities. This talk will describe new mechanisms for automatically identifying communities of practice within organizations and for elucidating the spread of information within those communities. Many of these mechanisms rely on the scale-free nature of social networks. [Preview Abstract] |
Monday, March 21, 2005 9:12AM - 9:24AM |
A24.00005: Voter Model on Heterogeneous Graphs. Vishal Sood, Sidney Redner We study basic properties of the voter model on heterogeneous graphs with an arbitrary degree distribution. By mapping the voter model to a coalescing random walk, we are able to understand the effect of the degree distribution on the dynamical behavior. We thereby find that the mean consensus time for finite graphs of $N$ sites scales as $\mu_1^2 N/\mu_2$, where $\mu_1$ is the mean degree and $\mu_2$ the second moment of the degree distribution. Thus the consensus time may scale sublinearly with system size if the degree distribution is sufficiently broad. [Preview Abstract] |
Monday, March 21, 2005 9:24AM - 9:36AM |
A24.00006: Anomalous Transport in Complex Networks Eduardo Lopez, Sergey Buldyrev, Shlomo Havlin, H. Eugene Stanley To study transport properties of complex networks, we analyze the equivalent conductance $G$ between two arbitrarily chosen nodes of random scale-free networks with degree distribution $P(k)\sim k^{-\lambda}$ in which each link has the same unit resistance. We predict a broad range of values of $G$, with a power-law tail distribution $\Phi_{\rm SF}(G)\sim G^{-g_G}$, where $g_G=2\lambda -1$, and confirm our predictions by simulations. The power-law tail in $\Phi_{\rm SF}(G)$ leads to large values of $G$, thereby significantly improving the transport in scale-free networks, compared to Erd\H{o}s-R\'{e}nyi random graphs where the tail of the conductivity distribution decays exponentially. Based on a simple physical ``transport backbone'' picture we show that the conductances are well approximated by $ck_Ak_B/(k_A+k_B)$ for any pair of nodes $A$ and $B$ with degrees $k_A$ and $k_B$. Thus, a single parameter $c$ characterizes transport on scale-free networks. [Preview Abstract] |
Monday, March 21, 2005 9:36AM - 9:48AM |
A24.00007: Complex networks are self-similar Chaoming Song, Shlomo Havlin, Hernan Makse A large number of real networks are called ``scale-free'' because they show a power-law distribution of the number of links per node. However, it is widely believed that complex networks are not length-scale invariant or self-similar. This conclusion originates from the ``small world'' property of these networks, which implies that the number of nodes increases exponentially with the ``diameter'' of the network, rather than the power-law relation expected for a self-similar structure. Nevertheless, here we present a novel approach to the analysis of such networks, revealing that their structure is indeed self- similar. This result is achieved by the application of a renormalization procedure which coarse-grains the system into boxes containing nodes within a given ``size.'' Concurrently, we identify a power-law relation between the number of boxes needed to cover the network and the size of the box defining a self- similar exponent. These fundamental properties, which are shown for the WWW, social, cellular and protein-protein interaction networks, help to understand the emergence of the scale-free property in complex networks. They suggest a common self- organization dynamics of diverse networks at different scales into a critical state and in turn bring together previously unrelated fields: the statistical physics of complex networks with renormalization group, fractals and critical phenomena. [Preview Abstract] |
Monday, March 21, 2005 9:48AM - 10:24AM |
A24.00008: Interaction prediction using conserved network motifs in protein-protein interaction networks Invited Speaker: High-throughput protein interaction detection methods are strongly affected by false positive and false negative results. Focused experiments are needed to complement the large-scale methods by validating previously detected interactions but it is often difficult to decide which proteins to probe as interaction partners. Developing reliable computational methods assisting this decision process is a pressing need in bioinformatics. This talk will describe the recent developments in analyzing and understanding protein interaction networks, then present a method that uses the conserved properties of the protein network to identify and validate interaction candidates. We apply a number of machine learning algorithms to the protein connectivity information and achieve a surprisingly good overall performance in predicting interacting proteins. Using a ``leave-one-ou approach we find average success rates between 20-50\% for predicting the correct interaction partner of a protein. We demonstrate that the success of these methods is based on the presence of conserved interaction motifs within the network. A reference implementation and a table with candidate interacting partners for each yeast protein are available at http://www.protsuggest.org [Preview Abstract] |
Monday, March 21, 2005 10:24AM - 10:36AM |
A24.00009: Stability and topology of scale-free networks under attack and defense strategies Lazaros Gallos, Reuven Cohen, Panos Argyrakis, Armin Bunde, Shlomo Havlin We study tolerance and topology of random scale-free networks under attack and defense strategies that depend on the degree $k$ of the nodes. This situation occurs, for example, when the robustness of a node depends on its degree or in an intentional attack with insufficient knowledge on the network. We determine, for all strategies, the critical fraction $p_c$ of nodes that must be removed for disintegrating the network. We find that for an intentional attack, little knowledge of the well-connected sites is sufficient to strongly reduce $p_c$. At criticality, the topology of the network depends on the removal strategy, implying that different strategies may lead to different kinds of percolation transitions. [Preview Abstract] |
Monday, March 21, 2005 10:36AM - 10:48AM |
A24.00010: Modeling Cascading Failures in the North American Power Grid Ryan Kinney, Reka Albert The North American power grid, one of the most complex technological networks in existence, permits long-distance power transmission as well as disturbance propagation. We model the grid using its actual topology and incorporate plausible assumptions about transmission substation load and overload. Our results indicate that a solitary substation loss can induce an overload cascade and reduce the grid's transmission efficiency by 25{\%}. Examining the damage inflicted by single node removals, we find three universal behaviors which suggest that 40{\%} of the transmission substations can induce an overload cascade when perturbed. While significant damage can result from a single node removal, subsequent removals have only incremental effects, which agree with the power grid's topological resilience to less than 1{\%} node loss. [Preview Abstract] |
Monday, March 21, 2005 10:48AM - 11:00AM |
A24.00011: Avalanche dynamics in complex networks Byungnam Kahng, Kwang-il Goh, Deok-sun Lee, Eun-J Lee, Doochul Kim Avalanche dynamics, triggered by small initial perturbation, but spreading to other constitutes successively, is one of intriguing problems in complex systems. Here, we study such dynamics on scale-free networks. We first consider the case where the failed vertex can be recovered through the Bak-Tang-Wisenfeld sandpile model. Using the branching process approach, we obtain the exponents associated with the power-law behaviors of the avalanche size and duration time distributions, which depend on the degree exponent. Second, for the case where the failed vertex cannot be recovered permanently, we study the model for the data packet transport proposed by Motter and Lai. We find that depending on the control parameter, which is the relative ratio between the traffic amount and the failure threshold, a phase transition can occur from a free flow to congested state. At the transition point, the avalanche size distribution turns out to be robust against the degree exponent as long as the degree exponent is between 2 and 3. [Preview Abstract] |
|
A24.00012: Dynamical patterns of epidemic outbreaks in complex heterogeneous networks Alain Barrat, Marc Barth\'elemy, Romualdo Pastor-Satorras, Alessandro Vespignani We present a throughout inspection of the dynamical behavior of epidemic phenomena in populations with complex and heterogeneous connectivity patterns. We show that the growth of the epidemic prevalence is virtually instantaneous in all networks characterized by diverging degree fluctuations, independently of the structure of the connectivity correlation functions characterizing the population network. By means of analytical and numerical results, we show that the outbreak time evolution follows a precise hierarchical dynamics. Once reached the most highly connected hubs, the infection pervades the network in a progressive cascade across smaller degree classes. Finally, we show the influence of the initial conditions and the relevance of statistical results in single case studies concerning heterogeneous networks. The emerging theoretical framework appears of general interest in view of the recently observed abundance of natural networks with complex topological features and might provide useful insights for the development of adaptive strategies aimed at epidemic containment. [Preview Abstract] |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2024 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700