Thu, 24 Jul 2008 23:13:24 BST CiteULike: AbnerCYH's graph http://www.citeulike.org/user/AbnerCYH/tag/graph CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/AbnerCYH/article/3038205 <i>(2002), pp. 389-395.</i> Market Equilibrium via a Primal-Dual-Type Algorithm Nikhil Devanur Christos Papadimitriou Amin Saberi Vijay Vazirani (2002), pp. 389-395. 2008-07-24T04:40:27-00:00 2002 389 395 IEEE Computer Society algorithms game graph optimization http://www.citeulike.org/user/AbnerCYH/article/609170 <i>SIGKDD Explor. Newsl., Vol. 7, No. 2. (December 2005), pp. 76-83.</i> Link mining applications: progress and challenges Ted Senator doi:10.1145/1117454.1117465 SIGKDD Explor. Newsl., Vol. 7, No. 2. (December 2005), pp. 76-83. 2006-05-01T15:44:36-00:00 2005 SIGKDD Explor. Newsl. 1931-0145 7 2 76 83 ACM Press algorithms complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/609165 <i>SIGKDD Explor. Newsl., Vol. 7, No. 2. (December 2005), pp. 3-12.</i> Link mining: a survey Lise Getoor Christopher Diehl doi:10.1145/1117454.1117456 SIGKDD Explor. Newsl., Vol. 7, No. 2. (December 2005), pp. 3-12. 2006-05-01T15:42:29-00:00 2005 SIGKDD Explor. Newsl. 1931-0145 7 2 3 12 ACM Press algorithms complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/549531 <i>(2001), pp. 903-910.</i><br /><br />The HITS and the PageRank algorithms are eigenvector methods for identifying "authoritative" or "influential" articles, given hyperlink or citation information. That such algorithms should give consistent answers is surely a desideratum, and in this paper, we address the question of when they can be expected to give stable rankings under small perturbations to the hyperlink patterns. Using tools from matrix perturbation theory and Markov chain theory, we provide conditions under which... Link Analysis, Eigenvectors and Stability Andrew Ng Alice Zheng Michael Jordan (2001), pp. 903-910. 2006-03-13T13:00:34-00:00 2001 903 910 algorithms complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/348222 <i></i><br /><br />The explosive growth and the widespread accessibility of the Web has led to surge of research activity in the area of information retrieval on the World Wide Web. The seminal papers of Kleinberg [31], and Brin and Page [9] introduced Link Analysis Ranking, where hyperlink structures are used to determine the relative authority of a Web page, and produce improved algorithms for the ranking of Web search results. In this paper we work within the hubs and authorities framework defined by... Link Analysis Ranking Algorithms Theory And Experiments Allan Borodin Gareth Roberts Jeffrey Rosenthal Panayiotis Tsaparas 2005-10-11T18:13:20-00:00 algorithms complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/485876 <i>Mol Biol Cell, Vol. 17, No. 1. (January 2006), pp. 1-13.</i><br /><br />A standard for bioregulatory network diagrams is urgently needed in the same way that circuit diagrams are needed in electronics. Several graphical notations have been proposed, but none has become standard. We have prepared many detailed bioregulatory network diagrams using the molecular interaction map (MIM) notation, and we now feel confident that it is suitable as a standard. Here, we describe the MIM notation formally and discuss its merits relative to alternative proposals. We show by simple examples how to denote all of the molecular interactions commonly found in bioregulatory networks. There are two forms of MIM diagrams. "Heuristic" MIMs present the repertoire of interactions possible for molecules that are colocalized in time and place. "Explicit" MIMs define particular models (derived from heuristic MIMs) for computer simulation. We show also how pathways or processes can be highlighted on a canonical heuristic MIM. Drawing a MIM diagram, adhering to the rules of notation, imposes a logical discipline that sharpens one's understanding of the structure and function of a network. Molecular interaction maps of bioregulatory networks: a general rubric for systems biology. KW Kohn MI Aladjem JN Weinstein Y Pommier doi:10.1091/mbc.E05-09-0824 Mol Biol Cell, Vol. 17, No. 1. (January 2006), pp. 1-13. 2006-01-30T13:34:11-00:00 2006 Mol Biol Cell 1059-1524 17 1 1 13 algorithms biology complex graph http://www.citeulike.org/user/AbnerCYH/article/675313 <i>Algorithms for Molecular Biology, Vol. 1, No. 1. (26 April 2006), 7.</i><br /><br />BACKGROUND:Most cellular processes are carried out by multi-protein complexes, groups of proteins that bind together to perform a specific task. Some proteins form stable complexes, while other proteins form transient associations and are part of several complexes at different stages of a cellular process. A better understanding of this higher-order organization of proteins into overlapping complexes is an important step towards unveiling functional and evolutionary mechanisms behind biological networks.RESULTS:We propose a new method for identifying and representing overlapping protein complexes (or larger units called functional groups) within a protein interaction network. We develop a graph-theoretical framework that enables automatic construction of such representation. We illustrate the effectiveness of our method by applying it to TNF-alpha/NF-kappaB and pheromone signaling pathways. CONCLUSIONS:The proposed representation helps in understanding the transitions between functional groups and allows for tracking a protein's path through a cascade of functional groups. Therefore, depending on the nature of the network, our representation is capable of elucidating temporal relations between functional groups. Our results show that the proposed method opens a new avenue for the analysis of protein interaction networks. Decomposition of overlapping protein complexes: A graph theoretical method for analyzing static and dynamic protein associations Elena Zotenko Katia Guimarães Raja Jothi Teresa Przytycka doi:10.1186/1748-7188-1-7 Algorithms for Molecular Biology, Vol. 1, No. 1. (26 April 2006), 7. 2006-05-30T18:21:44-00:00 2006 Algorithms for Molecular Biology 1748-7188 1 1 7 algorithms biology complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/566780 <i>Immunological Reviews, Vol. 210, No. 1. (April 2006), pp. 187-207.</i> Charting protein complexes, signaling pathways, and networks in the immune system Bauch Angela Superti-Furga Giulio doi:10.1111/j.0105-2896.2006.00369.x Immunological Reviews, Vol. 210, No. 1. (April 2006), pp. 187-207. 2006-03-28T13:03:25-00:00 2006 Immunological Reviews 0105-2896 210 1 187 207 Blackwell Publishing algorithms biology complex graph http://www.citeulike.org/user/AbnerCYH/article/933886 <i>BMC Bioinformatics, Vol. 7 (06 November 2006), 488.</i> Evaluation of clustering algorithms for protein-protein interaction networks Sylvain Brohee Jacques van Helden doi:10.1186/1471-2105-7-488 BMC Bioinformatics, Vol. 7 (06 November 2006), 488. 2006-11-06T23:08:06-00:00 2006 BMC Bioinformatics 1471-2105 7 488 algorithms biology complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/86114 <i>Bioinformatics, Vol. 21, No. 3. (01 February 2005), 364.</i> Iterative Cluster Analysis of Protein Interaction Data Vicente Arnau Sergio Mars Ignacio Marin doi:10.1093/bioinformatics/bti021 Bioinformatics, Vol. 21, No. 3. (01 February 2005), 364. 2005-01-29T20:31:28-00:00 2005 Bioinformatics 1367-4803 21 3 364 Oxford University Press algorithms biology complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/2609417 <i>Genome Biol, Vol. 6, No. 13. (2005)</i><br /><br />We have developed a general probabilistic system for query-based discovery of pathway-specific networks through integration of diverse genome-wide data. This framework was validated by accurately recovering known networks for 31 biological processes in Saccharomyces cerevisiae and experimentally verifying predictions for the process of chromosomal segregation. Our system, bioPIXIE, a public, comprehensive system for integration, analysis, and visualization of biological network predictions for S. cerevisiae, is freely accessible over the worldwide web. Discovery of biological networks from diverse functional genomic data. CL Myers D Robson A Wible MA Hibbs C Chiriac CL Theesfeld K Dolinski OG Troyanskaya doi:10.1186/gb-2005-6-13-r114 Genome Biol, Vol. 6, No. 13. (2005) 2008-03-28T20:41:18-00:00 2005 Genome Biol 1465-6914 6 13 algorithms biology complex graph http://www.citeulike.org/user/AbnerCYH/article/3019160 <i>Automata, Languages and Programming (2008), pp. 634-645.</i><br /><br />Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. This paper posits such an algorithm; we present a linear-time modular decomposition algorithm that proceeds in four straightforward steps. This is achieved by introducing the notion of factorizing permutations to an earlier recursive approach. The only data structure used is an ordered list of trees, and each of the four steps amounts to simple traversals of these trees. Previous algorithms were either exceedingly complicated or resorted to impractical data-structures. Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations Marc Tedder Derek Corneil Michel Habib Christophe Paul doi:10.1007/978-3-540-70575-8_52 Automata, Languages and Programming (2008), pp. 634-645. 2008-07-18T17:42:46-00:00 2008 Automata, Languages and Programming 634 645 algorithms graph order http://www.citeulike.org/user/AbnerCYH/article/2994231 <i>PLoS Comput Biol, Vol. 4, No. 7. (11 July 2008), e1000108.</i><br /><br />Networks play a crucial role in computational biology, yet their analysis and representation is still an open problem. Power Graph Analysis is a lossless transformation of biological networks into a compact, less redundant representation, exploiting the abundance of cliques and bicliques as elementary topological motifs. We demonstrate with five examples the advantages of Power Graph Analysis. Investigating protein-protein interaction networks, we show how the catalytic subunits of the casein kinase II complex are distinguishable from the regulatory subunits, how interaction profiles and sequence phylogeny of SH3 domains correlate, and how false positive interactions among high-throughput interactions are spotted. Additionally, we demonstrate the generality of Power Graph Analysis by applying it to two other types of networks. We show how power graphs induce a clustering of both transcription factors and target genes in bipartite transcription networks, and how the erosion of a phosphatase domain in type 22 non-receptor tyrosine phosphatases is detected. We apply Power Graph Analysis to high-throughput protein interaction networks and show that up to 85% (56% on average) of the information is redundant. Experimental networks are more compressible than rewired ones of same degree distribution, indicating that experimental networks are rich in cliques and bicliques. Power Graphs are a novel representation of networks, which reduces network complexity by explicitly representing re-occurring network motifs. Power Graphs compress up to 85% of the edges in protein interaction networks and are applicable to all types of networks such as protein interactions, regulatory networks, or homology networks. Unraveling Protein Networks with Power Graph Analysis Loïc Royer Matthias Reimann Bill Andreopoulos Michael Schroeder doi:10.1371/journal.pcbi.1000108 PLoS Comput Biol, Vol. 4, No. 7. (11 July 2008), e1000108. 2008-07-11T23:03:28-00:00 2008 PLoS Comput Biol 4 7 e1000108 Public Library of Science algorithms biology complex graph http://www.citeulike.org/user/AbnerCYH/article/805567 <i>Genome Biol, Vol. 5, No. 8. (2004)</i><br /><br />We introduce an algorithmic method, termed modular decomposition, that defines the organization of protein-interaction networks as a hierarchy of nested modules. Modular decomposition derives the logical rules of how to combine proteins into the actual functional complexes by identifying groups of proteins acting as a single unit (sub-complexes) and those that can be alternatively exchanged in a set of similar complexes. The method is applied to experimental data on the pro-inflammatory tumor necrosis factor-alpha (TNF-alpha)/NFkappaB transcription factor pathway. Modular decomposition of protein-protein interaction networks. J Gagneur R Krause T Bouwmeester G Casari doi:10.1186/gb-2004-5-8-r57 Genome Biol, Vol. 5, No. 8. (2004) 2006-08-18T17:19:04-00:00 2004 Genome Biol 1465-6914 5 8 algorithms biology graph http://www.citeulike.org/user/AbnerCYH/article/2972424 <i>Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on (1992), pp. 473-481.</i><br /><br />The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an <e1>n</e1>-vertex graph, can be found in time <e1>O</e1>(<e1>M</e1>(<e1>n</e1>)), where <e1>M</e1>(<e1>n</e1>)=O(<e1>n</e1>^2.376) is the time needed to multiply two <e1>n</e1> by <e1>n</e1> matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in <e1>NC</e1>¹ The algorithmic aspects of the regularity lemma N Alon doi:10.1109/SFCS.1992.267804 Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on (1992), pp. 473-481. 2008-07-08T11:35:09-00:00 1992 Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on 473 481 algorithms combinatorics graph http://www.citeulike.org/user/AbnerCYH/article/2967669 <i>Comb. Probab. Comput., Vol. 13, No. 1. (January 2004), pp. 61-91.</i> The Turán Theorem for Random Graphs Yoshiharu Kohayakawa Vojtech Rödl Mathias Schacht doi:10.1017/S0963548303005856 Comb. Probab. Comput., Vol. 13, No. 1. (January 2004), pp. 61-91. 2008-07-06T18:26:07-00:00 2004 Comb. Probab. Comput. 0963-5483 13 1 61 91 Cambridge University Press combinatorics graph stochastic http://www.citeulike.org/user/AbnerCYH/article/2967668 <i>Random Struct. Algorithms, Vol. 22, No. 4. (July 2003), pp. 359-434.</i> Regular pairs in sparse random graphs I Y Kohayakawa V Rödl doi:10.1002/rsa.10081 Random Struct. Algorithms, Vol. 22, No. 4. (July 2003), pp. 359-434. 2008-07-06T18:26:04-00:00 2003 Random Struct. Algorithms 1042-9832 22 4 359 434 John Wiley & Sons, Inc. combinatorics graph stochastic http://www.citeulike.org/user/AbnerCYH/article/2967665 <i>J. Comb. Theory Ser. A, Vol. 97, No. 2. (February 2002), pp. 307-352.</i> Hypergraphs, quasi-randomness, and conditions for regularity Yoshiharu Kohayakawa Vojtech Rödl Jozef Skokan doi:10.1006/jcta.2001.3217 J. Comb. Theory Ser. A, Vol. 97, No. 2. (February 2002), pp. 307-352. 2008-07-06T18:23:26-00:00 2002 J. Comb. Theory Ser. A 0097-3165 97 2 307 352 Academic Press, Inc. combinatorics graph stochastic http://www.citeulike.org/user/AbnerCYH/article/2967663 <i>(2002), pp. 74-83.</i> Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems Béla Csaba Marek Karpinski Piotr Krysta (2002), pp. 74-83. 2008-07-06T18:23:19-00:00 2002 74 83 Society for Industrial and Applied Mathematics algorithms combinatorics complexity graph testing http://www.citeulike.org/user/AbnerCYH/article/2967662 <i>(2007), pp. 488-495.</i> Property testing in hypergraphs and the removal lemma V Rödl M Schacht doi:10.1145/1250790.1250862 (2007), pp. 488-495. 2008-07-06T18:23:14-00:00 2007 488 495 ACM algorithms combinatorics graph testing http://www.citeulike.org/user/AbnerCYH/article/2967660 <i>Journal of Combinatorial Theory, Series B, Vol. 97, No. 2. (March 2007), pp. 245-268.</i><br /><br />Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F0-packing number of a k-uniform hypergraph is an NP-hard problem. Finding the fractional F0-packing number however can be done in polynomial time. In this paper we give a lower bound for the integer F0-packing number in terms of and show that . Integer and fractional packings of hypergraphs V Rödl M Schacht MH Siggers N Tokushige doi:10.1016/j.jctb.2006.05.006 Journal of Combinatorial Theory, Series B, Vol. 97, No. 2. (March 2007), pp. 245-268. 2008-07-06T18:22:10-00:00 2007 Journal of Combinatorial Theory, Series B 97 2 245 268 algorithms graph optimization http://www.citeulike.org/user/AbnerCYH/article/2967661 <i>(2005), pp. 138-146.</i> Testing versus estimation of graph properties Eldar Fischer Ilan Newman doi:10.1145/1060590.1060612 (2005), pp. 138-146. 2008-07-06T18:22:13-00:00 2005 138 146 ACM algorithms combinatorics graph testing http://www.citeulike.org/user/AbnerCYH/article/411346 <i>J. Algorithms, Vol. 16, No. 1. (January 1994), pp. 80-109.</i> The algorithmic aspects of the regularity lemma N Alon RA Duke H Lefmann V R&\#246;dl R Yuster doi:10.1006/jagm.1994.1005 J. Algorithms, Vol. 16, No. 1. (January 1994), pp. 80-109. 2005-11-29T18:50:00-00:00 1994 J. Algorithms 0196-6774 16 1 80 109 Academic Press, Inc. algorithms combinatorics graph stochastic testing http://www.citeulike.org/user/AbnerCYH/article/2965918 <i>(1996)</i> The regularity lemma and approximation schemes for dense problems A Frieze (1996) 2008-07-05T13:09:44-00:00 1996 0272-5428 IEEE Computer Society algorithms combinatorics graph stochastic testing http://www.citeulike.org/user/AbnerCYH/article/2965917 <i>J. ACM, Vol. 45, No. 4. (July 1998), pp. 653-750.</i> Property testing and its connection to learning and approximation Oded Goldreich Shari Goldwasser Dana Ron doi:10.1145/285055.285060 J. ACM, Vol. 45, No. 4. (July 1998), pp. 653-750. 2008-07-05T13:09:40-00:00 1998 J. ACM 0004-5411 45 4 653 750 ACM algorithms combinatorics graph stochastic testing http://www.citeulike.org/user/AbnerCYH/article/2965915 <i>Random Struct. Algorithms, Vol. 21, No. 3-4. (2002), pp. 293-335.</i> On characterizing hypergraph regularity Y Dementieva PE Haxell B Nagle V Rödl doi:10.1002/rsa.10058 Random Struct. Algorithms, Vol. 21, No. 3-4. (2002), pp. 293-335. 2008-07-05T13:09:06-00:00 2002 Random Struct. Algorithms 1042-9832 21 3-4 293 335 John Wiley & Sons, Inc. algorithms combinatorics graph stochastic testing http://www.citeulike.org/user/AbnerCYH/article/2965914 <i>(2002), pp. 277-286.</i> An optimal algorithm for checking regularity: (extended abstract) Y Kohayakawa V Rödl L Thoma (2002), pp. 277-286. 2008-07-05T13:08:43-00:00 2002 277 286 Society for Industrial and Applied Mathematics algorithms combinatorics graph stochastic testing http://www.citeulike.org/user/AbnerCYH/article/2965913 <i>Inf. Comput., Vol. 205, No. 8. (August 2007), pp. 1117-1129.</i> Hardness of fully dense problems Nir Ailon Noga Alon doi:10.1016/j.ic.2007.02.006 Inf. Comput., Vol. 205, No. 8. (August 2007), pp. 1117-1129. 2008-07-05T13:08:01-00:00 2007 Inf. Comput. 0890-5401 205 8 1117 1129 Academic Press, Inc. algorithms combinatorics graph stochastic testing http://www.citeulike.org/user/AbnerCYH/article/2965690 <i>Journal of Combinatorial Optimization, Vol. 16, No. 2. (2008), pp. 99-106.</i><br /><br />Abstract   Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. On minimum -connected k -dominating set problem in unit disc graphs Weiping Shang Frances Yao Pengjun Wan Xiaodong Hu doi:10.1007/s10878-007-9124-y Journal of Combinatorial Optimization, Vol. 16, No. 2. (2008), pp. 99-106. 2008-07-05T07:08:34-00:00 2008 Journal of Combinatorial Optimization 16 2 99 106 algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2963513 <i>Computing and Combinatorics (2008), pp. 255-264.</i><br /><br />Protein-protein interactions (PPIs) are one of the most important mechanisms in cellular processes. To model protein interaction sites, recent studies have suggested to find interacting protein group pairs from large PPI networks at the first step, and then to search conserved motifs within the protein groups to form interacting motif pairs. To consider noise effect and incompleteness of biological data, we propose to use quasi-bicliques for finding interacting protein group pairs. We investigate two new problems which arise from finding interacting protein group pairs: the maximum vertex quasi-biclique problem and the maximum balanced quasi-biclique problem. We prove that both problems are NP-hard. This is a surprising result as the widely known maximum vertex biclique problem is polynomial time solvable [16]. We then propose a heuristic algorithm which uses the greedy method to find the quasi-bicliques from PPI networks. Our experiment results on real data show that this algorithm has a better performance than a benchmark algorithm for identifying highly matched BLOCKS and PRINTS motifs. Quasi-bicliques: Complexity and Binding Pairs Xiaowen Liu Jinyan Li Lusheng Wang doi:10.1007/978-3-540-69733-6_26 Computing and Combinatorics (2008), pp. 255-264. 2008-07-04T09:43:14-00:00 2008 Computing and Combinatorics 255 264 algorithms complexity graph http://www.citeulike.org/user/AbnerCYH/article/2963510 <i>Computing and Combinatorics (2008), pp. 587-599.</i><br /><br />We model a network in which messages spread by a simple directed graph G = (V,E) [8] and a function α: V→ℕ mapping each v ∈ V to a positive integer less than or equal to the indegree of v. The graph G represents the individuals in the network and the communication channels between them. An individual v ∈ V will be convinced of a message when at least α(v) of its in-neighbors are convinced. Suppose we are to convince a message to all individuals by convincing a subset S ⊆ V of individuals at the beginning and then let the message spread. We study minimum-sized sets S needed to convince all individuals at the end. In particular, our results include a lower bound on the size of a minimum S and the NP-completeness of computing a minimum S. Our lower bound utilizes a technique in [9]. Finally, we analyze the special case where each individual is convinced of a message when more than half of its in-neighbors are convinced. Spreading Messages Ching-Lueh Chang Yuh-Dauh Lyuu doi:10.1007/978-3-540-69733-6_58 Computing and Combinatorics (2008), pp. 587-599. 2008-07-04T09:41:20-00:00 2008 Computing and Combinatorics 587 599 algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2963512 <i>Computing and Combinatorics (2008), pp. 611-620.</i><br /><br />Given two sets of points in the plane, we are interested in locating a highway h such that an objective function on the city distance between points of the two sets is minimized (where the city distance is measured with speed v > 1 on a highway and 1 in the underlying metric elsewhere). Extending the results of Ahn et al. ([7]), we consider the option that there are already some built highways. We give a unified approach to this problem to design polynomial-time algorithms for several combinations of objective functions and types of the inserted highway (turnpike or freeway). Optimal Insertion of a Segment Highway in a City Metric Matias Korman Takeshi Tokuyama doi:10.1007/978-3-540-69733-6_60 Computing and Combinatorics (2008), pp. 611-620. 2008-07-04T09:41:35-00:00 2008 Computing and Combinatorics 611 620 algorithms geometries graph http://www.citeulike.org/user/AbnerCYH/article/2960381 <i>Genome Res., Vol. 17, No. 7. (1 July 2007), pp. 1061-1071.</i><br /><br />Transcription regulatory networks play a pivotal role in the development, function, and pathology of metazoan organisms. Such networks are comprised of protein-DNA interactions between transcription factors (TFs) and their target genes. An important question pertains to how the architecture of such networks relates to network functionality. Here, we show that a Caenorhabditis elegans core neuronal protein-DNA interaction network is organized into two TF modules. These modules contain TFs that bind to a relatively small number of target genes and are more systems specific than the TF hubs that connect the modules. Each module relates to different functional aspects of the network. One module contains TFs involved in reproduction and target genes that are expressed in neurons as well as in other tissues. The second module is enriched for paired homeodomain TFs and connects to target genes that are often exclusively neuronal. We find that paired homeodomain TFs are specifically expressed in C. elegans and mouse neurons, indicating that the neuronal function of paired homeodomains is evolutionarily conserved. Taken together, we show that a core neuronal C. elegans protein-DNA interaction network possesses TF modules that relate to different functional aspects of the complete network. 10.1101/gr.6148107 Transcription factor modularity in a gene-centered C. elegans core neuronal protein-DNA interaction network Vanessa Vermeirssen Inmaculada Barrasa Cesar Hidalgo Jenny Babon Reynaldo Sequerra Lynn Doucette-Stamm Albert-Laszlo Barabasi Albertha Walhout doi:10.1101/gr.6148107 Genome Res., Vol. 17, No. 7. (1 July 2007), pp. 1061-1071. 2008-07-03T19:19:06-00:00 2007 Genome Res. 17 7 1061 1071 biology complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/2960295 <i>Physical Review E, Vol. 63, No. 6. (22 May 2001), 066117.</i> Epidemic dynamics and endemic states in complex networks Romualdo Pastor-Satorras Alessandro Vespignani doi:10.1103/PhysRevE.63.066117 Physical Review E, Vol. 63, No. 6. (22 May 2001), 066117. 2008-07-03T18:28:23-00:00 2001 Physical Review E 63 6 066117 American Physical Society biology complex dynamics graph http://www.citeulike.org/user/AbnerCYH/article/1807616 <i>Physical Review Letters, Vol. 86, No. 14. (2 April 2001), 3200.</i><br /><br />The Internet has a very complex connectivity recently modeled by the class of scale-free networks. This feature; which appears to be very efficient for a communications network; favors at the same time the spreading of computer viruses. We analyze real data from computer virus infections and find the average lifetime and persistence of viral strains on the Internet. We define a dynamical model for the spreading of infections on scale-free networks; finding the absence of an epidemic threshold and its associated critical behavior. This new epidemiological framework rationalizes data of computer viruses and could help in the understanding of other spreading phenomena on communication and social networks. Epidemic Spreading in Scale-Free Networks Romualdo Pastor-Satorras Alessandro Vespignani doi:10.1103/PhysRevLett.86.3200 Physical Review Letters, Vol. 86, No. 14. (2 April 2001), 3200. 2007-10-22T19:13:25-00:00 2001 Physical Review Letters 86 14 3200 American Physical Society biology complex dynamics graph http://www.citeulike.org/user/AbnerCYH/article/2959218 <i>Theoretical Aspects of Computer Science (2002), pp. 149-152.</i><br /><br />Szemerédi’s Regularity Lemma is an important tool in discrete mathematics. It says that, in some sense, all graphs can be approximated by random-looking graphs. Therefore the lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. In the last few years more and more new results were obtained by using the Regularity Lemma, and also some new variants and generalizations appeared. Komlós and Simonovits have written a survey on the topic [96]. The present survey is, in a sense, a continuation of the earlier survey. Here we describe some sample applications and generalizations. To keep the paper self-contained we decided to repeat (sometimes in a shortened form) parts of the first survey, but the emphasis is on new results. The Regularity Lemma and Its Applications in Graph Theory János Komlós Ali Shokoufandeh Miklós Simonovits Endre Szemerédi doi:10.1007/3-540-45878-6_3 Theoretical Aspects of Computer Science (2002), pp. 149-152. 2008-07-03T13:25:40-00:00 2002 Theoretical Aspects of Computer Science 149 152 algorithms combinatorics graph stochastic testing http://www.citeulike.org/user/AbnerCYH/article/2945519 <i>Physical Review Letters, Vol. 100, No. 23. (2008)</i><br /><br />We present a general information theoretic approach for identifying functional subgraphs in complex networks. We show that the uncertainty in a variable can be written as a sum of information quantities, where each term is generated by successively conditioning mutual informations on new measured variables in a way analogous to a discrete differential calculus. The analogy to a Taylor series suggests efficient optimization algorithms for determining the state of a target variable in terms of functional groups of other nodes. We apply this methodology to electrophysiological recordings of cortical neuronal networks grown in vitro. Each cell's firing is generally explained by the activity of a few neurons. We identify these neuronal subgraphs in terms of their redundant or synergetic character and reconstruct neuronal circuits that account for the state of target cells. Identification of Functional Information Subgraphs in Complex Networks Lu\is Bettencourt Vadas Gintautas Michael Ham doi:10.1103/PhysRevLett.100.238701 Physical Review Letters, Vol. 100, No. 23. (2008) 2008-06-30T16:57:31-00:00 2008 Physical Review Letters 100 23 APS algorithms complex graph http://www.citeulike.org/user/AbnerCYH/article/2945813 <i>Bioinformatics (Oxford, England), Vol. 22, No. 24. (15 December 2006), pp. 3106-3108.</i><br /><br />MOTIVATION: Modularity analysis is a powerful tool for studying the design of biological networks, offering potential clues for relating the biochemical function(s) of a network with the 'wiring' of its components. Relatively little work has been done to examine whether the modularity of a network depends on the physiological perturbations that influence its biochemical state. Here, we present a novel modularity analysis algorithm based on edge-betweenness centrality, which facilitates the use of directional information and measurable biochemical data. An algorithm for modularity analysis of directed and weighted biological networks based on edge-betweenness centrality. J Yoon A Blumer K Lee doi:10.1093/bioinformatics/btl533 Bioinformatics (Oxford, England), Vol. 22, No. 24. (15 December 2006), pp. 3106-3108. 2008-06-30T20:25:35-00:00 2006 Bioinformatics (Oxford, England) 1460-2059 22 24 3106 3108 algorithms biology complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/2945497 <i>(2006), pp. 797-802.</i> Coherent closed quasi-clique discovery from large dense graph databases Zhiping Zeng Jianyong Wang Lizhu Zhou George Karypis doi:10.1145/1150402.1150506 (2006), pp. 797-802. 2008-06-30T16:41:18-00:00 2006 797 802 ACM algorithms graph kdd http://www.citeulike.org/user/AbnerCYH/article/2910540 <i>BMC Systems Biology, Vol. 2, No. 1. (2008)</i><br /><br />BACKGROUND:Recent developments have meant that network theory is making an important contribution to the topological study of biological networks, such as protein-protein interaction (PPI) networks. The identification of differentially expressed genes in DNA array experiments is a source of information regarding the molecular pathways involved in disease. Thus, considering PPI analysis and gene expression studies together may provide a better understanding of multifactorial neurodegenerative diseases such as Multiple Sclerosis (MS) and Alzheimer disease (AD). The aim of this study was to assess whether the parameters of degree and betweenness, two fundamental measures in network theory, are properties that differentiate between implicated (seed-proteins) and non-implicated nodes (neighbors) in MS and AD. We used experimentally validated PPI information to obtain the neighbors for each seed group and we studied these parameters in four networks: MS-blood network; MS-brain network; AD-blood network; and AD-brain network. RESULTS:Specific features of seed-proteins were revealed, whereby they displayed a lower average degree in both diseases and tissues, and a higher betweenness in AD-brain and MS-blood networks. Additionally, the heterogeneity of the processes involved indicate that these findings are not pathway specific but rather that they are spread over different pathways.CONCLUSION:Our findings show differential centrality properties of proteins whose gene expression is impaired in neurodegenerative diseases. A computational analysis of the protein-protein interaction networks in neurodegenerative diseases Joaquin Goni Francisco Esteban Nieves de Mendizabal Jorge Sepulcre Sergio Treijano Ion Agirrezabal Pablo Villoslada doi:10.1186/1752-0509-2-52 BMC Systems Biology, Vol. 2, No. 1. (2008) 2008-06-20T13:44:26-00:00 2008 BMC Systems Biology 2 1 algorithms biology complex graph kdd http://www.citeulike.org/user/AbnerCYH/article/2413970 <i>Mol Syst Biol, Vol. 4 (12 February 2008)</i> Modular cell biology: retroactivity and insulation Domitilla Del Vecchio Alexander Ninfa Eduardo Sontag doi:10.1038/msb4100204 Mol Syst Biol, Vol. 4 (12 February 2008) 2008-02-22T11:05:12-00:00 2008 Mol Syst Biol 4 EMBO and Nature Publishing Group biology complex graph http://www.citeulike.org/user/AbnerCYH/article/2910093 <i>SIAM Journal on Computing, Vol. 29, No. 5. (2000), pp. 1449-1483.</i> Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge Michael Saks Fotios Zaharoglou SIAM Journal on Computing, Vol. 29, No. 5. (2000), pp. 1449-1483. 2008-06-20T10:57:37-00:00 2000 SIAM Journal on Computing 29 5 1449 1483 SIAM algorithms graph topology http://www.citeulike.org/user/AbnerCYH/article/2875499 <i>Algorithmica, Vol. 18, No. 1. (6 May 1997), pp. 3-20.</i><br /><br />Abstract  We study the maximum integral multicommodity flow problem and the minimum multicut problem restricted to trees. This restriction is quite rich and contains as special cases classical optimization problems such as matching and vertex cover for general graphs. It is shown that both the maximum integral multicommodity flow and the minimum multicut problem are NP-hard and MAX SNP-hard on trees, although the maximum integral flow can be computed in polynomial time if the edges have unit capacity. We present an efficient algorithm that computes a multicut and integral flow such that the weight of the multicut is at most twice the value of the flow. This gives a 2-approximation algorithm for minimum multicut and a 1/2-approximation algorithm for maximum integral multicommodity flow in trees. Primal-dual approximation algorithms for integral flow and multicut in trees N Garg V Vazirani M Yannakakis doi:10.1007/BF02523685 Algorithmica, Vol. 18, No. 1. (6 May 1997), pp. 3-20. 2008-06-09T11:47:20-00:00 1997 Algorithmica 18 1 3 20 algorithms complexity graph http://www.citeulike.org/user/AbnerCYH/article/2874900 <i>European Journal of Operational Research, Vol. 160, No. 1. (1 January 2005), pp. 227-231.</i><br /><br />We consider linear programming problems with uncertain objective function coefficients. For each coefficient of the objective function, an interval of uncertainty is known, and it is assumed that any coefficient can take on any value from the corresponding interval of uncertainty, regardless of the values taken by other coefficients. It is required to find a minmax regret solution. This problem received considerable attention in the recent literature, but its computational complexity status remained unknown. We prove that the problem is strongly NP-hard. This gives the first known example of a minmax regret optimization problem that is NP-hard in the case of interval-data representation of uncertainty but is polynomially solvable in the case of discrete-scenario representation of uncertainty. On the complexity of minmax regret linear programming Igor Averbakh Vasilij Lebedev doi:10.1016/j.ejor.2003.07.007 European Journal of Operational Research, Vol. 160, No. 1. (1 January 2005), pp. 227-231. 2008-06-09T08:39:02-00:00 2005 European Journal of Operational Research 160 1 227 231 algorithms complexity graph http://www.citeulike.org/user/AbnerCYH/article/2874901 <i>Operations Research Letters, Vol. 33, No. 6. (November 2005), pp. 634-640.</i><br /><br />This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment problem is strongly NP-hard. Complexity of the min-max and min-max regret assignment problems Hassene Aissi Cristina Bazgan Daniel Vanderpooten doi:10.1016/j.orl.2004.12.002 Operations Research Letters, Vol. 33, No. 6. (November 2005), pp. 634-640. 2008-06-09T08:39:55-00:00 2005 Operations Research Letters 33 6 634 640 algorithms complexity graph http://www.citeulike.org/user/AbnerCYH/article/2874865 <i>Operations Research Letters, Vol. 36, No. 2. (March 2008), pp. 271-275.</i><br /><br />The minmax regret optimization model of the doubly weighted centdian location on trees is considered. Assuming that both types of weights, demands and relative importance of the customers, are partially known through interval estimates, an exact algorithm of complexity O(n3logn) is derived. This bound is improved in some special cases. A note on the minmax regret centdian location on trees Eduardo Conde doi:10.1016/j.orl.2007.05.009 Operations Research Letters, Vol. 36, No. 2. (March 2008), pp. 271-275. 2008-06-09T08:35:47-00:00 2008 Operations Research Letters 36 2 271 275 algorithms complexity graph http://www.citeulike.org/user/AbnerCYH/article/2874810 <i>Discrete Applied Mathematics, Vol. 127, No. 3. (1 May 2003), pp. 505-522.</i><br /><br />We consider single-facility location problems on a network with uncertain edge lengths. Specifically, the lengths of edges are assumed to be random with unknown distributions and can take on any values within prespecified intervals of uncertainty. Uncertainty in edge lengths reflects uncertainty in transportation times, or transportation costs, along the edges. It is required to find a robust (minmax regret) solution, that is, a location which is [var epsilon]-optimal for any possible realization of edge lengths, with [var epsilon] as small as possible. We show that such robust location problems are strongly NP-hard, in contrast with robust location problems with only node weights uncertainty that are known to be polynomially solvable. Complexity of robust single facility location problems on networks with uncertain edge lengths Igor Averbakh doi:10.1016/S0166-218X(02)00384-0 Discrete Applied Mathematics, Vol. 127, No. 3. (1 May 2003), pp. 505-522. 2008-06-09T07:49:30-00:00 2003 Discrete Applied Mathematics 127 3 505 522 automata complexity graph http://www.citeulike.org/user/AbnerCYH/article/2868423 <i>ACM Trans. Database Syst., Vol. 30, No. 3. (September 2005), pp. 661-697.</i> Generalized multidimensional data mapping and query processing Rui Zhang Panos Kalnis Beng Ooi Kian-Lee Tan doi:10.1145/1093382.1093383 ACM Trans. Database Syst., Vol. 30, No. 3. (September 2005), pp. 661-697. 2008-06-06T04:27:00-00:00 2005 ACM Trans. Database Syst. 0362-5915 30 3 661 697 ACM algorithms data_structure geometries graph http://www.citeulike.org/user/AbnerCYH/article/2868422 <i>(2005), pp. 200-209.</i> Efficient query processing on spatial networks Jagan Sankaranarayanan Houman Alborzi Hanan Samet doi:10.1145/1097064.1097093 (2005), pp. 200-209. 2008-06-06T04:26:55-00:00 2005 200 209 ACM algorithms data_structure geometries graph http://www.citeulike.org/user/AbnerCYH/article/2868420 <i>(2006), pp. 211-218.</i> Distance join queries on spatial networks Jagan Sankaranarayanan Houman Alborzi Hanan Samet doi:10.1145/1183471.1183506 (2006), pp. 211-218. 2008-06-06T04:26:53-00:00 2006 211 218 ACM algorithms data_structure geometries graph