Considering a clique as a conservative definition of community structure, we examine how graph partitioning algorithms interact with cliques. Many popular community-findingalgorithms partition the entire graph into n...
详细信息
ISBN:
(纸本)9780769543758
Considering a clique as a conservative definition of community structure, we examine how graph partitioning algorithms interact with cliques. Many popular community-findingalgorithms partition the entire graph into non-overlapping communities. We show that on a wide range of empirical networks, from different domains, significant numbers of cliques are split across separate partitions, as produced by such algorithms. We examine the largest connected component of the subgraph formed by retaining only edges in cliques, and apply partitioning strategies that explicitly minimise the number of cliques split. We conclude that, due to the connectedness of many networks, any community finding algorithm that produces partitions must fail to find at least some significant structures. Moreover, contrary to traditional intuition, in some empirical networks, strong ties and cliques frequently do cross community boundaries.
Signaling pathways are large complex biochemical networks. It is difficult to analyze the underlying mechanism of such networks as a whole. In the present article, we have proposed an algorithm for modularization of s...
详细信息
Signaling pathways are large complex biochemical networks. It is difficult to analyze the underlying mechanism of such networks as a whole. In the present article, we have proposed an algorithm for modularization of signal transduction pathways. Unlike studying a signaling pathway as a whole, this enables one to study the individual modules (less complex smaller units) easily and hence to study the entire pathway better. A comparative study of modules belonging to different species (for the same signaling pathway) has been made, which gives an overall idea about development of the signaling pathways over the taken set of species of calcium and MAPK signaling pathways. The superior performance, in terms of biological significance, of the proposed algorithm over an existing community finding algorithm of Newman [Newman MEJ. Modularity and community structure in networks. Proc Nail Acad Sci USA 2006;103(23):857782] has been demonstrated using the aforesaid pathways of H. sapiens. (C) 2007 Elsevier Inc. All rights reserved.
暂无评论