Bulletin of the American Physical Society
2006 APS March Meeting
Monday–Friday, March 13–17, 2006; Baltimore, MD
Session B3: Uncovering the Structure of Complex Networks |
Hide Abstracts |
Sponsoring Units: GSNP Chair: Albert-Laszlo Barabasi, University of Notre Dame Room: Baltimore Convention Center Ballroom I |
Monday, March 13, 2006 11:15AM - 11:51AM |
B3.00001: Modularity and community structure in networks Invited Speaker: Many systems of scientific interest can be represented as networks---sets of nodes joined in pairs by lines or edges. Examples include metabolic and other biochemical networks, neural networks, food webs, the Internet and the worldwide web, and social networks. The physics community has made substantial contributions to the study of networked systems in the last decade, drawing particularly on ideas from statistical physics, field theory, and data analysis. One issue that has received considerable attention is the detection and characterization of ``modules'' or ``communities'' within networks---densely connected groups of nodes, with only sparser connections between groups. The ability to find and quantify such communities has proved to be of significant practical worth in the study of biochemical, technological, and social networks, among others, and there has been a lot of activity directed at the development of community-finding methods and algorithms to make these kinds of studies possible. This talk will describe some of the work in this area, focusing in particular on several powerful methods developed recently that appear to outperform previous ones by a substantial margin. A number of example applications will be shown demonstrating the utility of community structure detection in the analysis of real-world network data. [Preview Abstract] |
Monday, March 13, 2006 11:51AM - 12:27PM |
B3.00002: Modular structure of flat and hierarchial networks Invited Speaker: |
Monday, March 13, 2006 12:27PM - 1:03PM |
B3.00003: Uncovering the overlapping modules of complex networks Invited Speaker: Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of. A fundamental question of great current interest is how to interpret the global organisation of such networks as the coexistence of their structural sub-units (called modules, communities, clusters, etc) associated with more highly interconnected parts. Identifying these unknown building blocks (e.g., functionally related proteins, industrial sectors, groups of people) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large data sets find separated modules, while most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analyse the main statistical features of the interwoven sets of overlapping communities making a much needed step towards the uncovering of the modular structure of complex systems. After defining a set of new characteristic quantities for their statistics, we apply an efficient technique to explore overlapping communities on a large scale. We find that overlaps are indeed very significant, and the distributions we introduce reveal novel universal features of networks. Our studies of collaboration, word association, and protein interaction graphs demonstrate that the web of modules has highly non-trivial correlations and specific scaling properties. [Preview Abstract] |
Monday, March 13, 2006 1:03PM - 1:39PM |
B3.00004: Spectral methods and Network Communities Invited Speaker: Spectral methods provide us with a powerful tool-box to explore the topology of networks. In this presentation we will review an application of spectral techniques to the analysis of communities in complex networks. Communities are network sub-groups formed by highly interconnected nodes, which are sparsely connected to the rest of the network. They appear ubiquitously in natural and artificial nets, and are believed to play a key role as functional units, and detecting them has become a crucial problem in complex-system analyses. The efficient and relatively fast algorithm we will present here exploits spectral properties of some matrices encoding the network topology (as the Laplacian matrix), combined with standard hierarchical-clustering techniques, and the use of the ``modularity parameter'' allowing to quantify the goodness of any possible community subdivision. The algorithm performance, will be compared with that of other existing methods, as applied to different well-known examples of artificial and real networks. Our results are in all the tested cases, at least as good as the best ones obtained with any other methods, and faster in most of the cases than methods providing similar-quality results. This converts the algorithm in a valuable computational tool for detecting and analyzing communities and modular structures in complex networks. The connection of these results with the problem of determining the optimal network topology to achieve synchronization within the net and to optimize other dynamical processes will also be put forward. [Preview Abstract] |
Monday, March 13, 2006 1:39PM - 2:15PM |
B3.00005: Changes in metabolic modules under environmental variations Invited Speaker: During the last few years, network approaches have shown great promise as a tool to both analyze and provide understanding of complex systems as disparate as the world-wide web and cellular metabolism. Much effort has been focused on characterizing topological properties of such systems. However, in order to develop detailed descriptions of complex networks, we need to look beyond their topology and incorporate dynamical aspects. The cellular metabolism, where nodes correspond to metabolites and links indicate chemical reactions, is an excellent model system where theoretical predictions can be compared with experimental results. I will present recent insights into the principles governing the modular utilization of the cellular metabolism [1,2,3]. We find that, while most metabolic reactions have small fluxes, the metabolism's activity is dominated by an interconnected sub-network of reactions with very high fluxes [1]. For the bacteria {\it H. pylori} and {\it E. coli} and the yeast {\it S. cerevisiae}, the metabolism responds to changes in growth conditions by reorganizing the rates of select reactions predominantly within this high-flux backbone. Furthermore, these networks are organized around the metabolic core -- a set of reactions that are always in use [2]. Strikingly, the activity of the metabolic core reactions is highly synchronized, and the core reactions are significantly more essential and evolutionary conserved than the non-core ones. \newline\newline [1] E. Almaas, B. Kovacs, T. Vicsek, Z.N. Oltvai and A.-L. Barabasi. Nature 427, 839 (2004). \newline [2] E. Almaas, Z.N. Oltvai and A.-L. Barabasi. PLoS Comput. Biol. In press (2005). 10.1371/journal.pcbi.0010068.eor \newline [3] P.J. Macdonald, E. Almaas and A.-L. Barabasi. Europhys. Lett. 72, 308 (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. |
© 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