Bulletin of the American Physical Society
2006 APS March Meeting
Monday–Friday, March 13–17, 2006; Baltimore, MD
Session N35: Focus Session: Organization of Complex Networks |
Hide Abstracts |
Sponsoring Units: GSNP Chair: Sidney Redner, Boston University Room: Baltimore Convention Center 338 |
Wednesday, March 15, 2006 8:00AM - 8:36AM |
N35.00001: Structural properties of Complex networks Invited Speaker: Jos\'e Mendes The k-core decomposition was recently applied to a number of real-world networks (the Internet, the WWW, cellular networks, etc and was turned out to be an important tool for visualization of complex networks and interpretation of cooperative processes in them. Rich k-core architectures of real networks were revealed. The k-core is the largest subgraph where vertices have at least k interconnections. We find the structure of k-cores, their sizes, and their birth points --- the bootstrap percolation thresholds. I will show a derivation of exact equations describing the k-core organization of a randomly damaged uncorrelated network with an arbitrary degree distribution. This allows us to obtain the sizes and other structural characteristics of k-cores in a variety of damaged and undamaged random networks and find the nature of the k-core percolation in complex networks. These general results will be applied to the classical random graphs and to scale-free networks, in particular, to empirical router-level Internet maps. We find that not only the giant connected components in infinite networks with slowly decreasing degree distributions are resilient against random damage, as was known, but their entire k-core architectures are robust. [Preview Abstract] |
Wednesday, March 15, 2006 8:36AM - 8:48AM |
N35.00002: Skeleton and fractal scaling in complex networks Kwang-Il Goh, Giovanni Salvi, Byungnam Kahng, Doochul Kim We find that the fractal scaling in a class of scale-free networks originates from the underlying tree structure called skeleton, a special type of spanning tree based on the edge betweenness centrality. The fractal skeleton has the property of the critical branching tree. The original fractal networks are viewed as a fractal skeleton dressed with local shortcuts. An in- silico model with both the fractal scaling and the scale- invariance properties is also constructed. The framework of fractal networks is useful in understanding the utility and the redundancy in networked systems. [Preview Abstract] |
Wednesday, March 15, 2006 8:48AM - 9:00AM |
N35.00003: Analysis of structure of small-world networks Tao Jia, Rahul Kulkarni, EIvind Almaas We study the distribution function for minimal paths in small-world networks. We express this distribution in a convex combination form, and use numerical studies to obtain a functional fit for the convex coefficient in the limit of large system sizes and small disorder. Finally, we find analytic expressions for minimal paths distribution based on the functional fit for the convex coefficient. Our analysis can also be considered from the perspective of 1D random walks, our work thus provides a mapping between the structure of small-world networks and the exit problem for a class of 1D random walks. [Preview Abstract] |
Wednesday, March 15, 2006 9:00AM - 9:12AM |
N35.00004: Inverted Berezinskii-Kosterlitz-Thouless Behavior on Scale-Free Hierarchical-Lattice Small-World Net Michael Hinczewski, A. Nihat Berker We have obtained exact results for a hierarchical lattice incorporating three key features of real-world networks: a scale-free degree distribution, a high clustering coefficient, and the small-world effect. By varying the probability $p$ of long-distance bonds, the entire spectrum from an unclustered non-small-world network to a highly-clustered small-world system is studied. Expressions for the degree distribution $P(k) $ and clustering coefficient $C$ are obtained for all $p$, as well as for the average path length $\ell$ for $p=0,1$. The Ising model on this network is studied by exact renormalization-group transformation of the quenched bond probability distribution, using up to 562,500 renormalized probability bins for the distribution. For $p < 0.494$, we find power-law critical behavior of the magnetization and susceptibility, with exponents continuously varying with $p$, and exponential decay of correlations away from $T_c$. For $p \geq 0.494$, where the network exhibits a small-world character, the critical behavior radically changes: We find an inverted Berezinskii-Kosterlitz-Thouless singularity, between a low-temperature phase with non-zero magnetization and finite correlation length and a high-temperature phase with zero magnetization and infinite correlation length, with power-law decay of correlations. Approaching $T_c$ from below, the magnetization and the susceptibility respectively exhibit $\exp (-C/\sqrt{T_c-T})$ and $\exp(D/\sqrt{T_c-T})$ singularities. [Preview Abstract] |
Wednesday, March 15, 2006 9:12AM - 9:24AM |
N35.00005: Origin of Fractality in the Growth of Complex Networks Chaoming Song, Shlomo Havlin, Hernan Makse The emergence of self-similarity and modularity in complex networks raises the fun- damental question of the growth process according to which these structures evolve. The possibility of a unique growth mechanism for biological networks, WWW and the Internet is of interest to the specialist and the laymen alike, as it promises to uncover the universal origins of collective behavior. Here, we present the concept of renormalization from critical phenomena as a mechanism for the growth of fractal and non-fractal modular networks. We show that the key principle that gives rise to the fractal architecture of networks is a strong effective ``repulsion'' between the most connected nodes (hubs) on all length scales, rendering them very dispersed. [Preview Abstract] |
Wednesday, March 15, 2006 9:24AM - 9:36AM |
N35.00006: A rescaling procedure for complex networks Francesco Rao, Guido Caldarelli, Paolo De Los Rios We present here a renormalization scheme for graphs. We introduce a decimation procedure by weighting the different nodes through their centrality. In such a way we obtain rescaled graphs with the same statistical properties of the one at the finest scale. We present the results of such method for some numerical simulations of various models. We also apply this procedure to the real graph composed by Internet Autonomous System. We believe that this procedure can help in detecting the scale free-properties of such structures and can be fruitfully applied whenever the size of a system is that large that it is impossible to be visualized as well as described as a whole. [Preview Abstract] |
Wednesday, March 15, 2006 9:36AM - 9:48AM |
N35.00007: Statistical Properties of Sampled Networks Sang Hoon Lee, Pan-Jun Kim, Hawoong Jeong We study the statistical properties of the sampled scale-free networks, deeply related to the proper identification of various real-world networks. We exploit three methods of sampling, and investigate the topological properties such as degree and betweenness centrality distribution, average path length, assortativity, and clustering coefficient of sampled networks compared with those of original networks. It is found that the quantities related to those properties in sampled networks appear to be estimated quite differently for each sampling method. We explain why such a biased estimation of quantities would emerge from the sampling procedure, and give appropriate criteria for each sampling method to prevent the quantities from being overestimated or underestimated. [Preview Abstract] |
Wednesday, March 15, 2006 9:48AM - 10:00AM |
N35.00008: Routing and Congestion in Power Law Graphs Sameet Sreenivasan, Eduardo Lopez, Zoltan Toroczkai We investigate a simple model of packet routing on a power law (scale free) graph where packets arrive at each node at a given rate and are routed to a randomly chosen destination along the shortest path between the source and destination. This mimics the Shortest Path Routing protocol used in the internet. It was previously found that there is a critical rate of packet arrival beyond which there is an onset of congestion and packets start accumulating on the network. This critical rate depends on the maximum betweenness incurred on the network when shortest path routing is used. We analytically find a bound on the maximal betweenness incurred in shortest path routing and compare it to the optimal (least possible) maximal betweenness that can be acheived using an arbitrary routing protocol. This provides an effective quantitative measure of the optimality of Shortest Path Routing. [Preview Abstract] |
Wednesday, March 15, 2006 10:00AM - 10:12AM |
N35.00009: Connectivity and Cost Trade-offs in Multihop Wireless Networks May Lim, Dan Braha, Sanith Wijesinghe, Stephenson Tucker, Yaneer Bar-Yam Ad-hoc wireless networks are of increasing importance in communication and are frequently constrained by energy use. Here we propose a distributed, non-hierarchical adaptive method using preferential detachment for adjusting node transmission power to reduce overall power consumption without violating network load limitations. We derive a cost and path length trade-off diagram that establishes the bounds of effectiveness of the adaptive strategy and compare it with uniform node transmission strategy for several node topologies. We achieve cost savings as high as 90{\%} for specific topologies. [Preview Abstract] |
Wednesday, March 15, 2006 10:12AM - 10:24AM |
N35.00010: Locating overlapping dense subgraphs in gene (protein) association networks and predicting novel protein functional groups among these subgraphs Gergely Palla, Imre Derenyi, Illes J. Farkas, Tamas Vicsek Most tasks in a cell are performed not by individual proteins, but by functional groups of proteins (either physically interacting with each other or associated in other ways). In gene (protein) association networks these groups show up as sets of densely connected nodes. In the yeast, Saccharomyces cerevisiae, known physically interacting groups of proteins (called protein complexes) strongly overlap: the total number of proteins contained by these complexes by far underestimates the sum of their sizes (2750 vs. 8932). Thus, most functional groups of proteins, both physically interacting and other, are likely to share many of their members with other groups. However, current algorithms searching for dense groups of nodes in networks usually exclude overlaps. With the aim to discover both novel functions of individual proteins and novel protein functional groups we combine in protein association networks (i) a search for overlapping dense subgraphs based on the Clique Percolation Method (CPM) (Palla, G., et.al. Nature 435, 814-818 (2005), http://angel.elte.hu/clustering), which explicitly allows for overlaps among the groups, and (ii) a verification and characterization of the identified groups of nodes (proteins) with the help of standard annotation databases listing known functions. [Preview Abstract] |
Wednesday, March 15, 2006 10:24AM - 10:36AM |
N35.00011: Scaling Properties of Topological Neural Nets Alfred Hubler, Joseph Jun We study the agglomeration of metallic particles in an electric field. Earlier it has been shown that this system is a hardware implementation of a neural net [1]. In this paper we study the growth and topological properties of the emerging networks. In contrast to other networks the conductivity of the connections has a fixed value, but the completeness and number of connections depends on the training patterns. We find that the patterns grow in three stages: growth of shooters, ramification, and expansion [2]. The emerging patterns are hierarchical. For the limiting patterns certain properties are highly reproducible, such as the number of end points and the number of branching points, while other properties are not well reproducible, such as the number of tree structures. Further there are power law relations between the mass and the number of branching points and the number of end points. [1] M. Sperl, A. Chang, N. Weber, and A. Hubler, \textit{Hebbian Learning in the Agglomeration of Conducting Particles}, Phys.Rev.E. \textbf{59}, 3165-3168 (1999). [2] J. K. Jun and A. Hubler, \textit{Formation and structure of ramified charge transportation networks in an electromechanical system}, PNAS 102, 536--540 (2005). [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. |
© 2018 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
1 Research Road, Ridge, NY 11961-2701
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700