|
Conductance (probability)
In theoretical computer science, graph theory, and mathematics, the conductance is a parameter of a Markov chain that is closely tied to its mixing time, that is, how rapidly the chain converges to its stationary distribution, should it exist. Equivalently, the conductance can be viewed as a parameter of a directed graph, in which case it can be used to analyze how quickly random walks in the graph converge. The conductance of a graph is closely related to the Cheeger constant of the graph, which is also known as the edge expansion or the isoperimetic number. However, due to subtly different definitions, the conductance and the edge expansion do not generally coincide if the graphs are not regular. On the other hand, the notion of electrical conductance that appears in electrical networks is unrelated to the conductance of a graph. History The conductance was first defined by Mark Jerrum and Alistair Sinclair in 1988 to prove that the permanent of a matrix with entries fr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Conductance
Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discrete mathematics *Graph of a function * Graph of a relation *Graph paper *Chart, a means of representing data (also called a graph) Computing *Graph (abstract data type), an abstract data type representing relations or connections *graph (Unix), Unix command-line utility *Conceptual graph, a model for knowledge representation and reasoning *Microsoft Graph, a Microsoft API developer platform that connects multiple services and devices Other uses * HMS ''Graph'', a submarine of the UK Royal Navy See also * Complex network *Graf *Graff (other) *Graph database *Grapheme, in linguistics *Graphemics *Graphic (other) *-graphy (suffix from the Greek for "describe," "write" or "draw") *List of information graphics software *Stati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial-time Approximation Scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter and produces a solution that is within a factor of being optimal (or for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most , with being the length of the shortest tour. Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998. The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time or even counts as a PTAS. Variants Deterministic A practical problem with PTAS algorithms is that the exponent of the polynomial co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Krackhardt E/I Ratio
The Krackhardt E/I Ratio (or variously the E-I Index) is a social network measure which the relative density of internal connections within a social group compared to the number of connections that group has to the external world. It was so described in a 1988 paper by David Krackhardt and Robert N. Stern noting the increased effectiveness in moments of crisis of organizations which had stronger informal networks that crossed formal internal group structures. Comparisons with network theory The E/I ratio is related to the concept of conductance, which measures the likelihood that a random walk on a subgraph will exit that subgraph. References * Informal networks and organizational crises: An experimental simulation. David Krackhardt, Robert N. Stern - Social Psychology Quarterly, 1988DOI:10.2307/2786835 See also * Conductance (graph) * Percolation In physics, chemistry, and materials science, percolation () refers to the movement and filtration, filtering of fluids ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Percolation Theory
In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected clusters merge into significantly larger Glossary of graph theory, connected, so-called spanning clusters. The applications of percolation theory to materials science and in many other disciplines are discussed here and in the articles Network theory and Percolation (cognitive psychology). Introduction A representative question (and the etymology, source of the name) is as follows. Assume that some liquid is poured on top of some porosity, porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is mathematical model, modelled mathematically as a Grid graph, three-dimensional network of graph (discrete mathematics), vertices, usually called "sites", in which the graph (dis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Resistance Distance
In graph theory, the resistance distance between two vertices of a simple, connected graph, , is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to , with each edge being replaced by a resistance of one ohm. It is a metric on graphs. Definition On a graph , the resistance distance between two vertices and is : \Omega_:=\Gamma_+\Gamma_-\Gamma_-\Gamma_, :where \Gamma = \left(L + \frac\Phi\right)^+, with denotes the Moore–Penrose inverse, the Laplacian matrix of , is the number of vertices in , and is the matrix containing all 1s. Properties of resistance distance If then . For an undirected graph :\Omega_=\Omega_=\Gamma_+\Gamma_-2\Gamma_ General sum rule For any -vertex simple connected graph and arbitrary matrix : :\sum_(LML)_\Omega_ = -2\operatorname(ML) From this generalized sum rule a number of relationships can be derived depending on the choice of . Two of note are; :\begin \sum_\Omega_ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Markov Chain Mixing Time
In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution and, regardless of the initial state, the time-''t'' distribution of the chain converges to as ''t'' tends to infinity. Mixing time refers to any of several variant formalizations of the idea: how large must ''t'' be until the time-''t'' distribution is approximately ? One variant, ''total variation distance mixing time'', is defined as the smallest ''t'' such that the total variation distance of probability measures is small: :t_(\varepsilon) = \min \left\. Choosing a different \varepsilon, as long as \varepsilon < 1/2, can only change the mixing time up to a constant factor (depending on ) and so one often fixes and simply writes [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ergodic Flow
In mathematics, ergodic flows occur in geometry, through the geodesic and horocycle flows of closed hyperbolic surfaces. Both of these examples have been understood in terms of the theory of unitary representations of locally compact groups: if Γ is the fundamental group of a closed surface, regarded as a discrete subgroup of the Möbius group G = PSL(2,R), then the geodesic and horocycle flow can be identified with the natural actions of the subgroups ''A'' of real positive diagonal matrices and ''N'' of lower unitriangular matrices on the unit tangent bundle ''G'' / Γ. The Ambrose-Kakutani theorem expresses every ergodic flow as the flow built from an invertible ergodic transformation on a measure space using a ceiling function. In the case of geodesic flow, the ergodic transformation can be understood in terms of symbolic dynamics; and in terms of the ergodic actions of Γ on the boundary ''S''1 = ''G'' / ''AN'' and ''G'' / ''A'' = ''S''1 × ''S''1 \ diag ''S''1. Ergodic flows ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Flow Network
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A flow network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. As such, efficient algorithms for solving network flows can also be applied to solve problems that can be reduced to a flow network, including survey design, airline scheduling, image segmentation, and the matching prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph (data Structure)
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics. A graph data structure consists of a finite (and possibly mutable) set of ''vertices'' (also called ''nodes'' or ''points''), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as ''edges'' (also called ''links'' or ''lines''), and for a directed graph are also known as ''edges'' but also sometimes ''arrows'' or ''arcs''. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some ''edge value'', such as a symbolic label or a numeric attribute (cost, capacity, length, etc.). Operations The basic operations provided by a graph data structure ''G'' usually include:See, e.g. , Sec ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ergodic
In mathematics, ergodicity expresses the idea that a point of a moving system, either a dynamical system or a stochastic process, will eventually visit all parts of the space that the system moves in, in a uniform and random sense. This implies that the average behavior of the system can be deduced from the trajectory of a "typical" point. Equivalently, a sufficiently large collection of random samples from a process can represent the average statistical properties of the entire process. Ergodicity is a property of the system; it is a statement that the system cannot be reduced or factored into smaller components. Ergodic theory is the study of systems possessing ergodicity. Ergodic systems occur in a broad range of systems in physics and in geometry. This can be roughly understood to be due to a common phenomenon: the motion of particles, that is, geodesics on a hyperbolic manifold are divergent; when that manifold is compact, that is, of finite size, those orbits return to the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spectral Clustering
In multivariate statistics, spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. The similarity matrix is provided as an input and consists of a quantitative assessment of the relative similarity of each pair of points in the dataset. In application to image segmentation, spectral clustering is known as segmentation-based object categorization. Definitions Given an enumerated set of data points, the similarity matrix may be defined as a symmetric matrix A, where A_\geq 0 represents a measure of the similarity between data points with indices i and j. The general approach to spectral clustering is to use a standard clustering method (there are many such methods, ''k''-means is discussed below) on relevant eigenvectors of a Laplacian matrix of A. There are many different ways to define a Laplacian which have different mathematical interpretatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Percolation
In physics, chemistry, and materials science, percolation () refers to the movement and filtration, filtering of fluids through porous materials. It is described by Darcy's law. Broader applications have since been developed that cover connectivity of many systems modeled as lattices or graphs, analogous to connectivity of lattice components in the filtration problem that modulates capacity for percolation. Background During the last decades, percolation theory, the mathematical study of percolation, has brought new understanding and techniques to a broad range of topics in physics, materials science, complex networks, epidemiology, and other fields. For example, in geology, percolation refers to filtration of water through soil and permeable rocks. The water flows to groundwater recharge, recharge the groundwater in the water table and aquifers. In places where infiltration basins or septic drain fields are planned to dispose of substantial amounts of water, a percolation test ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
