Opened 9 years ago
Closed 9 years ago
#15662 closed enhancement (fixed)
Ihara zeta function of graphs
Reported by:  chapoton  Owned by:  

Priority:  major  Milestone:  sage6.1 
Component:  graph theory  Keywords:  zeta function 
Cc:  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  public/15662 (Commits, GitHub, GitLab)  Commit:  10181d9dba18f37b031d3761bcfdcfc75bf4a8cf 
Dependencies:  Stopgaps: 
Description
Let us implement the zeta function of graphs
Change History (26)
comment:1 Changed 9 years ago by
 Branch set to u/chapoton/15662
 Commit set to b2c1e310c03477183cb3e793103711989955eb57
 Status changed from new to needs_review
comment:2 Changed 9 years ago by
Yo !
Wikipedia says "a zeta function", and you cite a paper saying that there are many zeta functions defined on graph. Why shouldn't this method be renamed to ihara_zeta_function
instead ?
Besides, I don't understand what you do with the edges of your graph : why do you inverse the first and second coordinate ? (you cannot even assume that the vertices are integers when you write code for graphs. So if you want to ensure that they are sorted in some way ....)
Nathann
comment:3 Changed 9 years ago by
 Status changed from needs_review to needs_info
comment:4 followup: ↓ 5 Changed 9 years ago by
Hello,
1) I am not quite sure about the name indeed. I would say that this is usually called the zeta function of a graph. But there are variants, some of them called weighted zeta functions. I think keeping the name starting with zeta is good for TAB completion.
2) The algorithm needs to duplicate every edge, by orienting the original one in a chosen direction, and the new one in the other direction. I take as orientation the one given by self.edges(). I then use the shift by the number of edges as the bijection between original edges and their duplicatereverse.
3) Some people had needed that function and used another way to do it : see http://mathoverflow.net/questions/122682/iharazetafunctiongraphtheorycoefficientsusingalinegraph
comment:5 in reply to: ↑ 4 Changed 9 years ago by
Yoooooooooooo !
1) I am not quite sure about the name indeed. I would say that this is usually called the zeta function of a graph. But there are variants, some of them called weighted zeta functions. I think keeping the name starting with zeta is good for TAB completion.
Hmmmmm... Well, if the terminology isn't even set, should it become a Graph method ? I am trying to keep my graph functions out of the graph class when I believe that their are not of very wide use.
When you type "zeta function graphs" in Google (http://goo.gl/SM8aLb) the first result I get is the following : http://math.ucsd.edu/~aterras/snowbird.pdf
Which hints that there may be quite a lot of Zeta functions defined on graphs. And they do mention the one you implement, saying that it may be weighted too. What about .zeta_ihara
if you want the name to begin with zeta
?
2) The algorithm needs to duplicate every edge, by orienting the original one in a chosen direction, and the new one in the other direction.
Like when you do DiGraph(a_graph)
?
I take as orientation the one given by self.edges(). I then use the shift by the number of edges as the bijection between original edges and their duplicatereverse.
Oh. Well, I still do not understand what your two loops exactly do, but it looks like you are computing a bit too much. It feels like you are interested in the edges which share a vertex, except when they represent the same edge.
...
Hey, aren't you just computing the adjacency matrix of the line graph, which can be obtained by G.line_graph().adjacency_matrix()
?
Nathann
comment:6 Changed 9 years ago by
Okay I read the Mathoverflow thread a bit, and I think that the shortest way for you is to do this :
labeled_g = Graph() labeled_g.add_edges([(u,v,i) for i,(u,v) in enumerate(g.edges(labels=False))]) # faster than giving the edges when the graph is being built. Don't ask. for v in labeled_g: for vv,u,i in labeled_g.edges_incident(v): if v != vv: raise RuntimeError("Should Not Happen") # do what you have to, now that you know the labels of your edges.
comment:7 Changed 9 years ago by
 Commit changed from b2c1e310c03477183cb3e793103711989955eb57 to 55235f6a0d30333d2704303fbbeee7f8679114ec
Branch pushed to git repo; I updated commit sha1. New commits:
55235f6  trac #15662 better algo and better doc

comment:8 Changed 9 years ago by
 Branch changed from u/chapoton/15662 to public/15662
 Commit 55235f6a0d30333d2704303fbbeee7f8679114ec deleted
 Status changed from needs_info to needs_review
Helloooooooo Frederic !
Thank you for this patch. I personally find it clearer, and at least it should be faster. I also added a small commit to this patch (sorry, I just cannot not remove a 'if' when I see a way :P
).
I still have a few questions : is it really the *inverse* of the Ihara function (as the documentation claims) or is that a mistake ?
 If it is can you fix it in the docstring and in the function index at the top of the file
 If not, shouldn't it appear in the function's name too ?
I cannot check from the Wikipedia page that the polynomial you implemented is indeed what it should be. Of course this is mainly because I don't get a word of what this polynomial represents, but I would like to check the correction anyway ^^;
Could you help me a bit with that ? :P
Thaaaaaaaaanks !
Nathann
comment:9 Changed 9 years ago by
 Commit set to 232c4824582e31b896a820778b94ae334276129d
comment:10 Changed 9 years ago by
 Commit changed from 232c4824582e31b896a820778b94ae334276129d to 403fd968aefe0eaf3b9e72f4ec79ba8ac7d9aad5
Branch pushed to git repo; I updated commit sha1. New commits:
403fd96  trac #15662 added more doc and changed name again

comment:11 Changed 9 years ago by
Hello Nathann,
thanks for your interest and your help.
I have added to the doc one more reference where you can find the exact definition I am using.
You can also look at slide 9/10 in http://math.ucsd.edu/~aterras/ihara%20zeta%20and%20QC.pdf for the definition in short
You can also find examples of values in there : http://www.ams.org/journals/bull/20145101/S027309792013014265/S027309792013014265.pdf
comment:12 Changed 9 years ago by
Helloooooooooo !!
Thanks for this pointer toward the definition we use ! I tried to compare what http://www.ams.org/journals/bull/20145101/S027309792013014265/S027309792013014265.pdf gets for K_4 and it looks like what Sage's implementation gives is not the same ?... (we have a (t + 1)^2 * (t  1)^3
,they do not).
Nathann
comment:13 followup: ↓ 14 Changed 9 years ago by
Maybe just a matter of factorisation ? They do not give a fully factorised form, but some adhoc handmade factorisation.
comment:14 in reply to: ↑ 13 Changed 9 years ago by
Maybe just a matter of factorisation ? They do not give a fully factorised form, but some adhoc handmade factorisation.
They are different.
sage: g = graphs.CompleteGraph(4) sage: p1 = g.ihara_zeta_function() sage: ring = PolynomialRing(ZZ, 't') sage: g = graphs.CompleteGraph(4) sage: ring = PolynomialRing(ZZ, 't') sage: t = ring.gen() sage: p1 = g.ihara_zeta_function() sage: p2 = (1t^2)*(1t)*(12*t)*(1+t+2*t^2)^3 sage: p1 == p2 False
comment:15 followup: ↓ 16 Changed 9 years ago by
Their answer does not have the right degree. Maybe a typo in the article ?
For K5, there is a value in http://math.ucsd.edu/~aterras/snowbird.pdf, which also does not agree with ours (just missing a power in some factor), and also does not have the right degree. Another typo ?
Either we are wrong or we need to find a more serious place to look for the correct values.
comment:16 in reply to: ↑ 15 Changed 9 years ago by
Yooooooooo !
Their answer does not have the right degree. Maybe a typo in the article ?
Noooooooo idea O_o
For K5, there is a value in http://math.ucsd.edu/~aterras/snowbird.pdf, which also does not agree with ours (just missing a power in some factor), and also does not have the right degree. Another typo ?
Either we are wrong or we need to find a more serious place to look for the correct values.
Hmmm... May be worth sending them an email to ask. They may like to learn that this is being implemented somewhere by the way ;)
Nathann
comment:17 Changed 9 years ago by
Sorry, I guess my argument about the degree is wrong.. It is not necessarily twice the number of edges..
comment:18 Changed 9 years ago by
you forgot the power of (1t^2)
when checking the K4 result in the Bull. AMS paper:
sage: g=graphs.CompleteGraph(4) sage: p1=g.ihara_zeta_function() sage: p2=(1t^2)**2*(1t)*(12*t)*(1+t+2*t^2)^3 sage: p1==p2 True
comment:19 Changed 9 years ago by
Oh. Sorry O_o
I am trying to load the paper again but the ams's website is in a bad mood. Does the value for K_5 coincide with the snowbird paper too ? If so we just need to update the oneline description of the method in graph.py (which does not match the one in the function's docstring) and the patch can go !
Nathann
comment:20 followup: ↓ 21 Changed 9 years ago by
Nathann, it seems that you have not pulled the latest version (done yesterday evening) which corrects the names and minor details !
I really think that the results are correct. The only discrepancy with all the results in the literature is in the case of K5, where several people seems to have copypasted the same result. This could verywell be wrong everywhere.
comment:21 in reply to: ↑ 20 Changed 9 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
Yoooooooo !
Nathann, it seems that you have not pulled the latest version (done yesterday evening) which corrects the names and minor details !
T_T
Sorry again. I had noted somewhere in my head that this had to be done, and forgot that you had changed the name of the function since. Sorry for this second wrong information :P
I really think that the results are correct. The only discrepancy with all the results in the literature is in the case of K5, where several people seems to have copypasted the same result. This could verywell be wrong everywhere.
Okayokay. Positive review then. What would you think of sending an email to those guys to ask them what they think of it ? It's good to let them know this is available somewhere, and can either let us fix a bug here or let them fix a bug in their paper.
Thanks for this patch ! Sorry for the long review and errors ^^;
Nathann
comment:22 Changed 9 years ago by
Thanks for the review !
comment:23 Changed 9 years ago by
Merge conflict... please merge in 6.1.beta5 & resolve.
comment:24 Changed 9 years ago by
 Commit changed from 403fd968aefe0eaf3b9e72f4ec79ba8ac7d9aad5 to 10181d9dba18f37b031d3761bcfdcfc75bf4a8cf
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
10181d9  trac #15662: Rebase on 6.1.beta5

comment:25 Changed 9 years ago by
 Status changed from needs_review to positive_review
Done. It conflicted with kirchhoff_symanzik_polynomial
.
Nathann
comment:26 Changed 9 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #15662 implement Ihara zeta function of graphs