Talk:Conductance (graph theory)

I've tidied things up a bit. Further concerns? Richard Pinch (talk) 11:49, 6 July 2008 (UTC)

Merger proposal

I think this article and Conductance (probability) are not different enough to merit two separate articles. Someone with the enthusiasm please merge them :) shreevatsa (talk) 01:01, 2 August 2008 (UTC)

Good idea. Richard Pinch (talk) 20:55, 3 August 2008 (UTC)

Passing through from a blog, I agree that as they currently stand, they are not different enough to warrant two articles. However, this is partially because the probability article has not been well-defined. In particular, the two conductances are 'the same' only when we are discussing a 'standard' random walk on a regular graph. Otherwise, Yuval Peres (among many others, I'm sure - I just learned these definitions from him) have a better definition of conductance for a Markov chain in terms of the transition matrix rather than the adjacency matrix. This is used for a number of methods, from eigenvalue approximations (as it is in graph theory), to the method of evolving sets (which, in my very limited knowledge, has no analogue). Does anybody following this page consider it worthwhile to keep the probability article, if it is sufficiently differentiated? (refs: "Evolving Sets and Mixing" by Yuval Peres and Ben Morris, "DRAFT Lecture Notes for Summer School at UBC" by Yuval Peres, both available on that web page) —Preceding unsigned comment added by 70.48.237.250 (talk) 04:10, 30 November 2008 (UTC)

The definition currently on this page is a special case of the more general definition, isn't it? So why not just keep the more general one? In any case, please feel free to add whatever you have read, to whatever article you think is appropriate. Shreevatsa (talk) 04:43, 30 November 2008 (UTC)

Merge. Conductance is a graph property, which can be applied to the transition matrix of the Markov Chain when it is symmetric, or to a slightly modified matrix when the chain is reversible. In any case, Conductance_(graph) should be the final article, with a section on how Sinclair applied this concept to bound mixing times for random walks.--Robin (talk) 12:43, 27 March 2009 (UTC)

application to social sciences and social network analysis

I heard this term used in this talk by Michael W. Mahoney:

http://vielmetti.typepad.com/vacuum/2008/12/community-structure-in-large-social-and-information-networks-michael-mahoney-stanford-speaking-at-th.html

as applied to the analysis of graphs inside social networks like Facebook or even our own Wikipedia. As such there are very clearly conductance measures that are not simply infinite-length Markov chains. Trying to make some sense of it all by incremental improvements to this page and related. Edward Vielmetti (talk) 02:52, 8 December 2008 (UTC)

Another merger

As the text states, "Cheeger constant" is a synonym, and the two articles should be merged. Patrickelvin (talk) 15:04, 30 March 2020 (UTC)

Strongly opposed, since Cheeger constant is not a synonym. Even if you restrict to unweighted and undirected graphs, you get a subtle difference between the two notions if the graph is not regular: The conductance in its denominator weighs the nodes proportional to their degrees, whereas the Cheeger constant weighs each vertex equally. Moreover, the conductance also applies to directed graphs with edge weights as well as to Markov chains, whereas the notion defined in the article Cheeger constant does not do so, and I'm not aware of references that use the term Cheeger constant in such cases. I added more information to this article to make the difference a bit clearer. ylloh (talk) 20:33, 10 April 2024 (UTC)

The computation in the image look wrong to me

I cannot make sense of the conductance calculations in the figure, in particular the denominator. Kuzeko (talk) 16:29, 27 May 2023 (UTC)

This figure needs an overhaul, at the very least the calculation and example cuts should not be part of the image. What throws you off is likely the 17 in the denominator min(3, 17) for {A}. The 17 arises, because you count each edge internal to ${\overline {S_{1}}}$ twice, whereas each edge crossing the cut is only counted once. ylloh (talk) 20:40, 10 April 2024 (UTC)