CiteULike: AbnerCYH's library [705 articles]

The algorithmic aspects of the regularity lemma

N Alon — 2005-11-29T18:50:00-00:00

J. Algorithms, Vol. 16, No. 1. (January 1994), pp. 80-109.

The computation of market equilibria

Bruno Codenotti — 2008-06-10T02:59:35-00:00

SIGACT News, Vol. 35, No. 4. (December 2004), pp. 23-37.

Constructing boosting algorithms from SVMs: an application to one-class classification

G Ratsch — 2008-05-10T07:08:19-00:00

Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 24, No. 9. (September 2002), pp. 1184-1199.

We show via an equivalence of mathematical programs that a support vector (SV) algorithm can be translated into an equivalent boosting-like algorithm and vice versa. We exemplify this translation procedure for a new algorithm—one-class leveraging—starting from the one-class support vector machine (1-SVM). This is a first step toward unsupervised learning in a boosting framework. Building on so-called barrier methods known from the theory of constrained optimization, it returns a function, written as a convex combination of base hypotheses, that characterizes whether a given test point is likely to have been generated from the distribution underlying the training data. Simulations on one-class classification problems demonstrate the usefulness of our approach.

The support vector machine under test

David Meyer — 2008-05-09T19:40:26-00:00

Neurocomputing, Vol. 55, No. 1-2. (September 2003), pp. 169-186.

Support vector machines (SVMs) are rarely benchmarked against other classification or regression methods. We compare a popular SVM implementation (libsvm) to 16 classification methods and 9 regression methods--all accessible through the software --by the means of standard performance measures (classification error and mean squared error) which are also analyzed by the means of bias-variance decompositions. SVMs showed mostly good performances both on classification and regression tasks, but other methods proved to be very competitive.

Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology

Rohit Singh — 2008-05-08T18:52:23-00:00

Research in Computational Molecular Biology (2007), pp. 16-31.

We describe an algorithm, IsoRank, for global alignment of two protein-protein interaction (PPI) networks. IsoRank aims to maximize the overall match between the two networks; in contrast, much of previous work has focused on the local alignment problem— identifying many possible alignments, each corresponding to a local region of similarity. IsoRank is guided by the intuition that a protein should be matched with a protein in the other network if and only if the neighbors of the two proteins can also be well matched. We encode this intuition as an eigenvalue problem, in a manner analogous to Google’s PageRank method. We use IsoRank to compute the first known global alignment between the S. cerevisiae and D. melanogaster PPI networks. The common subgraph has 1420 edges and describes conserved functional components between the two species. Comparisons of our results with those of a well-known algorithm for local network alignment indicate that the globally optimized alignment resolves ambiguity introduced by multiple local alignments. Finally, we interpret the results of global alignment to identify functional orthologs between yeast and fly; our functional ortholog prediction method is much simpler than a recently proposed approach and yet provides results that are more comprehensive.

A Parameterized Algorithm for Protein Structure Alignment

Jinbo Xu — 2008-03-27T16:06:17-00:00

Journal of Computational Biology, Vol. 14, No. 5. (2007), pp. 564-577.

This paper proposes a parameterized polynomial time approximation scheme (PTAS) for aligning two protein structures, in the case where one protein structure is represented by a contact map graph and the other by a contact map graph or a distance matrix. If the sequential order of alignment is not required, the time complexity is polynomial in the protein size and exponential with respect to two parameters Du/Dl and Dc/Dl, which usually can be treated as constants. In particular, Du is the distance threshold determining if two residues are in contact or not, Dc is the maximally allowed distance between two matched residues after two proteins are superimposed, and Dl is the minimum inter-residue distance in a typical protein. This result clearly demonstrates that the computational hardness of the contact map based protein structure alignment problem is related not to protein size but to several parameters modeling the problem. The result is achieved by decomposing the protein structure using tree decomposition and discretizing the rigid-body transformation space. Preliminary experimental results indicate that on a Linux PC, it takes from ten minutes to one hour to align two proteins with approximately 100 residues.

Fast and practical indexing and querying of very large graphs

Silke Tri\ssl — 2008-01-15T05:11:41-00:00

(2007), pp. 845-856.

The Discrete Chaos

Norbert Wiener — 2007-12-27T16:37:04-00:00

American Journal of Mathematics, Vol. 65, No. 2. (1943), pp. 279-298.

On the strength of comparisons in property testing

Eldar Fischer — 2007-11-10T12:13:45-00:00

Information and Computation, Vol. 189, No. 1. (25 February 2004), pp. 107-116.

An [epsilon]-test for a property P of functions from to the positive integers is a randomized algorithm, which makes queries on the value of an input function at specified locations, and distinguishes with high probability between the case of the function satisfying P, and the case that it has to be modified in more than [epsilon]d places to make it satisfy P. We prove that an [epsilon]-test for a property of integer sequences, such as the property of the sequence being a monotone nondecreasing sequence, that depends (in a strict sense) only on the order relations between the sequence members, cannot perform less queries (in the worst case) than the best [epsilon]-test which uses only comparisons between the queried values. In addition, we show that an adaptive algorithm for testing that a sequence is monotone non-decreasing performs no better than the best non-adaptive one, with respect to query complexity. From this follows a tight lower bound on tests for this property.

Power-law distributions in empirical data

Aaron Clauset — 2007-06-13T16:25:35-00:00

(7 Jun 2007)

Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the empirical detection and characterization of power laws is made difficult by the large fluctuations that occur in the tail of the distribution. In particular, standard methods such as least-squares fitting are known to produce systematically biased estimates of parameters for power-law distributions and should not be used in most circumstances. Here we describe statistical techniques for making accurate parameter estimates for power-law data, based on maximum likelihood methods and the Kolmogorov-Smirnov statistic. We also show how to tell whether the data follow a power-law distribution at all, defining quantitative measures that indicate when the power law is a reasonable fit to the data and when it is not. We demonstrate these methods by applying them to twenty-four real-world data sets from a range of different disciplines. Each of the data sets has been conjectured previously to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data while in others the power law is ruled out.

Logic, Graphs, and Algorithms

Martin Grohe — 2007-09-25T16:09:42-00:00

(2007)

Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic can be decided in linear time on graphs of bounded tree width. This article is an introduction into the theory underlying such meta theorems and a survey of the most important results in this area.

Finding Pathway Structures in Protein Interaction Networks

Songjian Lu — 2007-08-13T16:11:48-00:00

Algorithmica, Vol. 48, No. 4. (2007), pp. 363-374.

Abstract The increased availability of data describing biological interactions provides important clues on how complex chains of genes and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find an optimal path structure in time and space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure. Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures, we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity by applying it to protein interaction networks in the DIP database.

Graph mining: Laws, generators, and algorithms

Deepayan Chakrabarti — 2006-07-21T13:00:13-00:00

ACM Comput. Surv., Vol. 38, No. 1. (2006)

Logspace Optimization Problems and Their Approximability Properties

Till Tantau — 2007-07-26T16:39:55-00:00

Theory of Computing Systems, Vol. 41, No. 2. (2007), pp. 327-350.

Abstract Logspace optimization problems are the logspace analogues of the well-studied polynomial-time optimization problems. Similarly to them, logspace optimization problems can have vastly different approximation properties even though their underlying decision problems have the same computational complexity. Natural problems - including the shortest path problems for directed graphs, undirected graphs, tournaments, and forests - exhibit such a varying complexity. In order to study the approximability of logspace optimization problems in a systematic way, polynomial-time approximation classes and polynomial-time reductions between optimization problems are transferred to logarithmic space. It is proved that natural problems are complete for different logspace approximation classes. This is used to show that under the assumption L ≠ NL some logspace optimization problems cannot be approximated with a constant ratio; some can be approximated with a constant ratio, but do not permit a logspace approximation scheme; and some have a logspace approximation scheme, but optimal solutions cannot be computed in logarithmic space.

Entropy as a fixed point

Keye Martin — 2007-03-16T09:52:39-00:00

Theor. Comput. Sci., Vol. 350, No. 2. (February 2006), pp. 292-324.

We study complexity and information and introduce the idea that while complexity is relative to a given class of processes, information is process independent: Information is complexity relative to the class of all conceivable processes. In essence, the idea is that information is an extension of the concept ‘algorithmic complexity’ from a class of desirable and concrete processes, such as those represented by binary decision trees, to a class more general that can only in pragmatic terms be regarded as existing in the conception. It is then precisely the fact that information is defined relative to such a large class of processes that it becomes an effective tool for analyzing phenomena in a wide range of disciplines. We test these ideas on the complexity of classical states. A domain is used to specify the class of processes, and both qualitative and quantitative notions of complexity for classical states emerge. The resulting theory is used to give new proofs of fundamental results from classical information theory, to give a new characterization of entropy in quantum mechanics, to establish a rigorous connection between entanglement transformation and computation, and to derive lower bounds on algorithmic complexity. All of this is a consequence of the setting which gives rise to the fixed point theorem: The least fixed point of the copying operator above complexity is information.

Motif Search in Graphs: Application to Metabolic Networks

Vincent Lacroix — 2007-01-05T02:31:38-00:00

IEEE/ACM Trans. Comput. Biol. Bioinformatics, Vol. 3, No. 4. (October 2006), pp. 360-368.

A homology theory for spanning trees of a graph

L Lovász — 2006-07-22T18:33:14-00:00

Acta Math. Acad. Sci. Hungar., Vol. 30, No. 3-4. (1977), pp. 241-251.

The author constructs a cellular complex $K(G,a)=K$, called the arborescence complex of a digraph $G$ (relative to vertex $a$); in fact, $K$ is simply connected (Theorem 5). By calculation, the author demonstrates (Theorem 4) that the reduced homology groups $H_r(K)$ of the arborescence complex of $G$ are zero, for $0≤ r≤ k-2$, whenever $G$ is a digraph containing a vertex $a$ such that no point can be separated from $a$ by less than $k$ points $(k≥ 2)$. Lastly, using Theorem 4, both the undirected and directed versions of a conjecture of A. Frank ("Combinatorial algorithms, algorithmic proofs", Dissertation, Budapest, 1975) follow. Theorem: Given a $k$-connected graph $G$, $k$ points $v_1,⋅s,v_k∈ V(G)$, and $k$ positive integers whose sum $n_1+n_2+⋅s+n_k=|V(G)|$, there exists a partition ${V_1,⋅s,V_k}$ of $V(G)$ such that $v_i∈ V_i$, $|V_i|=n_k$ and $V_i$ spans a connected subgraph.

Fixed Point Calculus

Ronald Backhouse — 2005-12-27T18:26:11-00:00

(2000)

Fixed point calculus is about the solution of recursive equations dened by a monotonic endofunction on a partially ordered set. This tutorial discusses applications of xed point calculus in the construction of computer programs, beginning with standard applications and progressing to recent research. The basic properties of least and greatest xed points are presented. Wellfoundedness and inductive properties of relations are expressed in terms of xed points. A class of xed point equations, ...

Difference equations

Ronald Mickens — 2007-09-22T16:57:48-00:00

In recent years, the study of difference equations has acquired a new significance, due in large part to their use in the formulation and analysis of discrete-time systems, the numerical integration of differential equations by finite-difference schemes, and the study of deterministic chaos. The second edition of Difference Equations: Theory and Applications provides a thorough listing of all major theorems along with proofs. The text treats the case of first-order difference equations in detail, using both analytical and geometrical methods. Both ordinary and partial difference equations are considered, along with a variety of special nonlinear forms for which exact solutions can be determined. Numerous worked examples and problems allow readers to fully understand the material in the text. They also give possible generalization of the theorems and application models.The text's expanded coverage of application helps readers appreciate the benefits of using difference equations in the modeling and analysis of "realistic" problems from a broad range of fields. The second edition presents, analyzes, and discusses a large number of applications from the mathematical, biological, physical, and social sciences. Discussions on perturbation methods and difference equation models of differential equation models of differential equations represent contributions by the author to the research literature. Reference to original literature show how the elementary models of the book can be extended to more realistic situations.Difference Equations, Second Edition gives readers a background in discrete mathematics that many workers in science-oriented industries need as part of their general scientific knowledge. With its minimal mathematical background requirements of general algebra and calculus, this unique volume will be used extensively by students and professional in science and technology, in areas such as applied mathematics, control theory, population science, economics, and electronic circuits, especially discrete signal processing.

Algorithmic Information Theory: a brief non-technical guide to the field

Marcus Hutter — 2007-03-07T05:43:07-00:00

Scholarpedia (6 Mar 2007)

This article is a brief guide to the field of algorithmic information theory (AIT), its underlying philosophy, and the most important concepts. AIT arises by mixing information theory and computation theory to obtain an objective and absolute notion of information in an individual object, and in so doing gives rise to an objective and robust notion of randomness of individual objects. This is in contrast to classical information theory that is based on random variables and communication, and has no bearing on information and randomness of individual objects. After a brief overview, the major subfields, applications, history, and a map of the field are presented.

An Algebraic Perspective of Group Relaxations

Rekha Thomas — 2007-03-27T10:27:02-00:00

(3 Oct 2001)

This is an expository article on recent developments in the theory of group relaxations in integer programming from an algebraic perspective.

Max-algebra: the linear algebra of combinatorics?

Peter Butkovic — 2007-03-15T00:55:31-00:00

Linear Algebra and its Applications, Vol. 367 (1 July 2003), pp. 313-335.

Let a[circled plus]b=max(a,b), a[circle times operator]b=a+b for . By max-algebra we understand the analogue of linear algebra developed for the pair of operations ([circled plus],[circle times operator]) extended to matrices and vectors. Max-algebra, which has been studied for more than 40 years, is an attractive way of describing a class of nonlinear problems appearing for instance in machine-scheduling, information technology and discrete-event dynamic systems. This paper focuses on presenting a number of links between basic max-algebraic problems like systems of linear equations, eigenvalue-eigenvector problem, linear independence, regularity and characteristic polynomial on one hand and combinatorial or combinatorial optimisation problems on the other hand. This indicates that max-algebra may be regarded as a linear-algebraic encoding of a class of combinatorial problems. The paper is intended for wider readership including researchers not familiar with max-algebra.

The origins of combinatorics on words

Jean Berstel — 2006-12-07T09:34:39-00:00

European Journal of Combinatorics, Vol. 28, No. 3. (April 2007), pp. 996-1022.

We investigate the historical roots of the field of combinatorics on words. They comprise applications and interpretations in algebra, geometry and combinatorial enumeration. These considerations gave rise to early results such as those of Axel Thue at the beginning of the 20th century. Other early results were obtained as a by-product of investigations on various combinatorial objects. For example, paths in graphs are encoded by words in a natural way, and conversely, the Cayley graph of a group or a semigroup encodes words by paths. We give in this text an account of this two-sided interaction.

Computational Dynamics

Ahmed Shabana — 2006-11-30T17:33:44-00:00

(2001)

An algorithm for modularity analysis of directed and weighted biological networks based on edge-betweenness centrality.

J Yoon — 2008-06-30T20:25:35-00:00

Bioinformatics (Oxford, England), Vol. 22, No. 24. (15 December 2006), pp. 3106-3108.

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.

Data Structures for Range Searching

Jon Bentley — 2007-08-19T16:22:04-00:00

ACM Comput. Surv., Vol. 11, No. 4. (December 1979), pp. 397-409.

Randomized rounding without solving the linear program

Neal Young — 2007-03-27T11:08:02-00:00

(1995), pp. 170-178.

Simple image set of linear mappings in a max-min algebra

Martin Gavalec — 2007-03-27T10:53:05-00:00

Discrete Applied Mathematics, Vol. 155, No. 5. (15 March 2007), pp. 611-622.

For a given linear mapping, determined by a square matrix A in a max-min algebra, the set SA consisting of all vectors with a unique pre-image (in short: the simple image set of A) is considered. It is shown that if the matrix A is generally trapezoidal, then the closure of SA is a subset of the set of all eigenvectors of A. In the general case, there is a permutation [pi], such that the closure of SA is a subset of the set of all eigenvectors permuted by [pi]. The simple image set of the matrix square and the topological aspects of the problem are also described.

Market Equilibrium via a Primal-Dual-Type Algorithm

Nikhil Devanur — 2008-07-24T04:40:27-00:00

(2002), pp. 389-395.

Link mining applications: progress and challenges

Ted Senator — 2006-05-01T15:44:36-00:00

SIGKDD Explor. Newsl., Vol. 7, No. 2. (December 2005), pp. 76-83.

Link mining: a survey

Lise Getoor — 2006-05-01T15:42:29-00:00

SIGKDD Explor. Newsl., Vol. 7, No. 2. (December 2005), pp. 3-12.

Link Analysis, Eigenvectors and Stability

Andrew Ng — 2006-03-13T13:00:34-00:00

(2001), pp. 903-910.

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 Ranking Algorithms Theory And Experiments

Allan Borodin — 2005-10-11T18:13:20-00:00

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...

On the Best Case of Heapsort

B Bollobás — 2008-07-22T05:11:42-00:00

Journal of Algorithms, Vol. 20, No. 2. (March 1996), pp. 205-217.

Although discovered some 30 years ago, the Heapsort algorithm is still not completely understood. Here we investigate thebest caseof Heapsort. Contrary to claims made by some authors that its time complexity isO(n), i.e., linear in the number of items, we prove that it is actuallyO(nlogn) and is, in fact, approximately half that of the worst case. Our proof contains a construction for an asymptotically best-case heap. In addition, the proof and construction provide theworst-casetime complexity and an asymptotically worst-case example forBottom-upversions of Heapsort.

Semantic integration to identify overlapping functional modules in protein interaction networks

Young-Rae Cho — 2007-07-25T05:48:46-00:00

BMC Bioinformatics, Vol. 8 (24 July 2007), 265.

Molecular interaction maps of bioregulatory networks: a general rubric for systems biology.

KW Kohn — 2006-01-30T13:34:11-00:00

Mol Biol Cell, Vol. 17, No. 1. (January 2006), pp. 1-13.

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.

Charting protein complexes, signaling pathways, and networks in the immune system

Bauch — 2006-03-28T13:03:25-00:00

Immunological Reviews, Vol. 210, No. 1. (April 2006), pp. 187-207.

Evaluation of clustering algorithms for protein-protein interaction networks

Sylvain Brohee — 2006-11-06T23:08:06-00:00

BMC Bioinformatics, Vol. 7 (06 November 2006), 488.

Iterative Cluster Analysis of Protein Interaction Data

Vicente Arnau — 2005-01-29T20:31:28-00:00

Bioinformatics, Vol. 21, No. 3. (01 February 2005), 364.

Discovery of biological networks from diverse functional genomic data.

CL Myers — 2008-03-28T20:41:18-00:00

Genome Biol, Vol. 6, No. 13. (2005)

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.

On the complexity of deriving position specific score matrices from positive and negative sequences

Tatsuya Akutsu — 2008-07-19T08:17:33-00:00

Discrete Applied Mathematics, Vol. 155, No. 6-7. (1 April 2007), pp. 676-685.

Position-specific score matrices (PSSMs) have been applied to various problems in computational molecular biology. In this paper, we study the following problem: given positive examples (sequences) and negative examples (sequences), find a PSSM which correctly discriminates between positive and negative examples. We prove that this problem is solved in polynomial time if the size of a PSSM is bounded by a constant. On the other hand, we prove that this problem is NP-hard if the size is not bounded. We also prove hardness results for deriving multiple PSSMs and related problems.

Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

Marc Tedder — 2008-07-18T17:42:46-00:00

Automata, Languages and Programming (2008), pp. 634-645.

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.

Unraveling Protein Networks with Power Graph Analysis

Loïc Royer — 2008-07-11T23:03:28-00:00

PLoS Comput Biol, Vol. 4, No. 7. (11 July 2008), e1000108.

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.

Encyclopedia of Algorithms

2008-07-16T13:37:20-00:00

(03 July 2008)

The Encyclopedia of Algorithms will provide a comprehensive set of solutions to important algorithmic problems for students and researchers interested in quickly locating useful information. The first edition of the reference will focus on high-impact solutions from the most recent decade; later editions will widen the scope of the work. Nearly 500 entries will be organized alphabetically by problem, with subentries allowing for distinct solutions and special cases to be listed by the year. An entry will include: * a description of the basic algorithmic problem * the input and output specifications * the key results * examples of applications * citations to the key literature Open problems, links to downloadable code, experimental results, data sets, and illustrations may be provided. All entries will be written by experts; links to Internet sites that outline their research work will also be provided. The entries will be peer-reviewed. This defining reference will be published in print and on line. The print publication will include an index of subjects and authors as well as a chronology for locating recent solutions. The online edition will supplement this index with hyperlinks as well as include hyperlinks in the text of the entries to related entries, xRefer citations, and other useful URLs mentioned above.

An optimal algorithm for checking regularity: (extended abstract)

Y Kohayakawa — 2008-07-10T16:00:22-00:00

(2002), pp. 277-286.

The algorithmic aspects of the regularity lemma

N Alon — 2008-07-08T11:35:09-00:00

Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on (1992), pp. 473-481.

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><sup>2.376</sup>) 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><sup>1</sup>

Small subsets inherit sparse $ε$-regularity

Stefanie Gerke — 2008-07-06T18:26:08-00:00

J. Comb. Theory Ser. B, Vol. 97, No. 1. (January 2007), pp. 34-56.

The Turán Theorem for Random Graphs

Yoshiharu Kohayakawa — 2008-07-06T18:26:07-00:00

Comb. Probab. Comput., Vol. 13, No. 1. (January 2004), pp. 61-91.

Regular pairs in sparse random graphs I

Y Kohayakawa — 2008-07-06T18:26:04-00:00

Random Struct. Algorithms, Vol. 22, No. 4. (July 2003), pp. 359-434.

The Blow-up Lemma

János Komlós — 2008-07-06T18:23:29-00:00

Comb. Probab. Comput., Vol. 8, No. 1-2. (1999), pp. 161-176.