5
$\begingroup$

Originally posted here: https://math.stackexchange.com/questions/276167/fixed-point-theorem-on-graphs

--

I have a graph $G=(V,E)$ where to each vertex $v$ I have associated a value, $\hat{v}$ (ie I have a "network" in the terminology here http://snap.stanford.edu/snap/index.html ).

Let $\phi : \hat{V} \rightarrow \hat{V}$ be the function which takes the value associated to each node and replaces it with median of the values of the adjacent nodes.

Empirically, iterating $\phi$ converges. Why?

edit: The graph is large and follows this model: http://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model . Also, for ~1% of nodes, $\phi$ is the identity. There is some related work here: http://www.cs.cmu.edu/~zhuxj/pub/CMU-CALD-02-107.pdf

edit: Looks like I can just replace the $P(j \rightarrow i)$ in the label propagation paper with $P(j \rightarrow i) = 1\; if \; \text{j is the median, }0 \text{ else}$, then I can copy their convergence result.

edit: Wait, no. If I do that then P changes each step so it's not a direct copy...

$\endgroup$
  • $\begingroup$ This process doesn't converge for the graph consisting of two vertices and a single edge. Or any path. Or any cycle. (With appropriate choice of weights.) It might be worth adding some hypotheses. $\endgroup$ – Daniel Litt Feb 9 '13 at 22:50
  • 1
    $\begingroup$ Am I misunderstanding something here. Say we have a graph with two nodes and one edge. Let the nodes have initially, different values. Now after one iteration (assuming all replacement happens in parallel), the values of the nodes get exchanged; repeating the iteration, they again exchange values. Thus, we have "oscillation" and no convergence.... $\endgroup$ – Suvrit Feb 9 '13 at 22:54
  • $\begingroup$ Ah, Daniel typed the same type of counterexample while I was typing my comment! $\endgroup$ – Suvrit Feb 9 '13 at 22:55
  • $\begingroup$ Oh, right, whoops, this happened on stackexchange to. My graph is very large and has a degree distribution which is (probably) power law. Edited question. $\endgroup$ – dranxo Feb 10 '13 at 2:32
  • $\begingroup$ What is the median of an even number of values? $\endgroup$ – Brendan McKay Feb 10 '13 at 12:15
7
$\begingroup$

If I am not mistaken, this problem was discussed in the article

Zbl 0194.13702 Lyubich, Yu.I.; Tabachnikov, M.I. Subharmonic functions on a directed graph. Siberian Math. J. 10, 432-442 (1969).

(unfortunately in Russian; I don't know whether there is an English translation)

$\endgroup$
  • $\begingroup$ May I ask (for those who cannot read Russian): What was the conclusion of the discussion in the article? Does $\phi$ converge? $\endgroup$ – Joseph O'Rourke Feb 10 '13 at 1:15
  • $\begingroup$ This is an interesting reference. Are there any English articles related to it? $\endgroup$ – dranxo Feb 10 '13 at 2:35
  • 1
    $\begingroup$ Joseph, I can answer in few days (I will read the article in our library). $\endgroup$ – Boris Novikov Feb 10 '13 at 8:11
  • $\begingroup$ rcompton, I don't know. $\endgroup$ – Boris Novikov Feb 10 '13 at 8:12
  • 1
    $\begingroup$ yes, there is a translation here: springerlink.com/content/n764q83pkq31l7r2 that said, i have the impression that everything in that paper is pretty linear, so how can that answer a median-based question? $\endgroup$ – Delio Mugnolo Feb 28 '13 at 18:51
4
$\begingroup$

Here are a few thoughts:

  1. It is easiest to ignore the case of unequal middle values, for example if every vertex has odd degree. Then the set of labels can only stay the same or get smaller so eventually the states must cycle (perhaps in a cycle of length 1=fixed point).

  2. It is enough to consider the case that the vertex values are only $0$ and $1$. If I tell you at the start only which vertices are "high" (above a threshhold $t$) and which are low (less than or equal to $t$) that information alone will be enough decide which vertices are high and which are low at each future stage. We can keep track of all the values by running a few of these thresh-hold graphs in parallel.

I can certainly see

  • fixed points: Just split into two (or $k$) groups of moderate size and make sure that each vertex has the majority of its neighbors in its own group. To get fancier (with lots of label values), make the maximum and minimum groups very large, make sure everyone has at least one neighbor with its own label and then make extra edges into the maximum and minimum groups to make sure the medians stay where they should.

  • cycles of length $2$ Two groups each with the majority of its labels going to the other group. Or enter image description here

After I made this illustration I had the insight that there is simply alternation between a $3/7$ high/low split and $7/3$ or $4/6$ and $6/4$, but I still like the picture.

In a few experiments on the Peterson graph (starting with distinct labels) a cycle of length two happened over $95\\%$ of the time. That is probably exactly the same as saying that with $0,1$ labels a two cycle happened this often with an even split, two thirds of the time with a $4/6$ split and one sixth of the time with a $3/7$ split. In that case it would be easy to figure out the exact probabilities.

Other graphs could be explored. For a pentagonal prism the chance of a two cycle is higher. Even with a $8/2$ split it is $22\\%$ (OK, I can see why) whereas this can not happen in a Peterson Graph.

Q: Can there be cycles of length three or larger? I did not see any but I did not look all that hard. However I would guess not.

It might be worth considering weighted edges, then the examples above can have merely $k$ vertices.


Consider large graphs (random or structured) with random labels $0$ and $1.$ Then the situation is like voting with everyone swayed by their friends (over many rounds) or some lattice with points magnetized up or down then affecting their neighbors (so this must be studied someplace). If the labels are assigned with very unequal frequencies then one would expect a sea of the majority value with islands of the minority value which shrink (or grow) for a while before stabilizing or going away (or going into a few two cycles). Big islands with lakes with little islands (containing ponds) in them would be possible by pre-planning but perhaps unlikely by chance. As the probabilities become closer to equal it would take a longer and longer time to stabilize with a phase transition at some point which might be very interesting to consider.


A final thought is that the tie breaking problem for an even number of neighbors could be avoided by saying that the value at the vertex is also counted in the median calculations when needed to break a tie. Weighted edges would also avoid this problem (if the weights were random enough to avoid ties).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.