Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Originally posted here: http://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...

share|improve this question
    
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. –  Daniel Litt Feb 9 '13 at 22:50
    
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.... –  Suvrit Feb 9 '13 at 22:54
    
Ah, Daniel typed the same type of counterexample while I was typing my comment! –  Suvrit Feb 9 '13 at 22:55
    
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. –  rcompton Feb 10 '13 at 2:32
    
What is the median of an even number of values? –  Brendan McKay Feb 10 '13 at 12:15
show 4 more comments

2 Answers

up vote 5 down vote accepted

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)

share|improve this answer
    
May I ask (for those who cannot read Russian): What was the conclusion of the discussion in the article? Does $\phi$ converge? –  Joseph O'Rourke Feb 10 '13 at 1:15
    
This is an interesting reference. Are there any English articles related to it? –  rcompton Feb 10 '13 at 2:35
1  
Joseph, I can answer in few days (I will read the article in our library). –  Boris Novikov Feb 10 '13 at 8:11
    
rcompton, I don't know. –  Boris Novikov Feb 10 '13 at 8:12
    
Mark, thank you. –  Boris Novikov Feb 11 '13 at 6:46
show 3 more comments

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 alt text

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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