Biomedical subjects

Gergely Palla

Publications and source records attributed to Gergely Palla.

5 recordsLinked to original sources

PubMed2006

CFinder: locating cliques and overlapping modules in biological networks.

UNLABELLED: Most cellular tasks are performed not by individual proteins, but by groups of functionally associated proteins, often referred to as modules. In a protein association network modules appear as groups of densely interconnected nodes, also called communities or clusters. These modules often overlap with each other and form a network of their own, in which nodes (links) represent the modules (overlaps). We introduce CFinder, a fast program locating and visualizing overlapping, densely interconnected groups of nodes in undirected graphs, and allowing the user to easily navigate between the original graph and the web of these groups. We show that in gene (protein) association networks CFinder can be used to predict the function(s) of a single protein and to discover novel modules. CFinder is also very efficient for locating the cliques of large sparse graphs. AVAILABILITY: CFinder (for Windows, Linux and Macintosh) and its manual can be downloaded from http://angel.elte.hu/clustering. SUPPLEMENTARY INFORMATION: Supplementary data are available on Bioinformatics online.

Biology↗

PubMed2005

Uncovering the overlapping community structure of complex networks in nature and society.

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 key question is how to interpret the global organization of such networks as the coexistence of their structural subunits (communities) associated with more highly interconnected parts. Identifying these a priori unknown building blocks (such as functionally related proteins, industrial sectors and groups of people) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large networks find separated communities, whereas most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analysing the main statistical features of the interwoven sets of overlapping communities that makes a step towards uncovering the modular structure of complex systems. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique for exploring overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks. Our studies of collaboration, word-association and protein interaction graphs show that the web of communities has non-trivial correlations and specific scaling properties.

Community Networks↗

PubMed2005

Clique percolation in random networks.

The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdos-Rényi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold p(c) (k) = [(k - 1)N](-1/(k - 1)). At the transition point the scaling of the giant component with N is highly nontrivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.

Community Networks↗

PubMed2004

Reverse engineering of linking preferences from network restructuring.

We provide a method to deduce the preferences governing the restructuring dynamics of a network from the observed rewiring of the edges. Our approach is applicable for systems in which the preferences can be formulated in terms of a single-vertex energy function with f (k) being the contribution of a node of degree k to the total energy, and the dynamics obeys the detailed balance. The method is first tested by Monte Carlo simulations of restructuring graphs with known energies; then it is used to study variations of real network systems ranging from the coauthorship network of scientific publications to the asset graphs of the New York Stock Exchange. The empirical energies obtained from the restructuring can be described by a universal function f (k) approximately -k ln k , which is consistent with and justifies the validity of the preferential attachment rule proposed for growing networks.

Journal Article↗

PubMed2004

Statistical mechanics of topological phase transitions in networks.

We provide a phenomenological theory for topological transitions in restructuring networks. In this statistical mechanical approach energy is assigned to the different network topologies and temperature is used as a quantity referring to the level of noise during the rewiring of the edges. The associated microscopic dynamics satisfies the detailed balance condition and is equivalent to a lattice gas model on the edge-dual graph of a fully connected network. In our studies-based on an exact enumeration method, Monte Carlo simulations, and theoretical considerations-we find a rich variety of topological phase transitions when the temperature is varied. These transitions signal singular changes in the essential features of the global structure of the network. Depending on the energy function chosen, the observed transitions can be best monitored using the order parameters Phi(s)=s(max)/M, i.e., the size of the largest connected component divided by the number of edges, or Phi(k)=k(max)/M, the largest degree in the network divided by the number of edges. If, for example, the energy is chosen to be E=-s(max), the observed transition is analogous to the percolation phase transition of random graphs. For this choice of the energy, the phase diagram in the ( ,T) plane is constructed. Single-vertex energies of the form E= summation operator (i)f(k(i)), where k(i) is the degree of vertex i, are also studied. Depending on the form of f(k(i)), first-order and continuous phase transitions can be observed. In case of f(k(i))=-(k(i)+alpha)ln(k(i)), the transition is continuous, and at the critical temperature scale-free graphs can be recovered. Finally, by abruptly decreasing the temperature, nonequilibrium processes (e.g., nucleation and growth of particular topological phases) can also be interpreted by the present approach.

Journal Article↗