Opened 6 years ago

Closed 6 years ago

#15662 closed enhancement (fixed)

Ihara zeta function of graphs

Reported by: chapoton Owned by:
Priority: major Milestone: sage-6.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) Commit: 10181d9dba18f37b031d3761bcfdcfc75bf4a8cf
Dependencies: Stopgaps:

Description

Let us implement the zeta function of graphs

Change History (26)

comment:1 Changed 6 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to u/chapoton/15662
  • Commit set to b2c1e310c03477183cb3e793103711989955eb57
  • Status changed from new to needs_review

New commits:

b2c1e31trac #15662 implement Ihara zeta function of graphs

comment:2 Changed 6 years ago by ncohen

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 6 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:4 follow-up: Changed 6 years ago by chapoton

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 duplicate-reverse.

3) Some people had needed that function and used another way to do it : see http://mathoverflow.net/questions/122682/ihara-zeta-function-graph-theory-coefficients-using-a-line-graph

comment:5 in reply to: ↑ 4 Changed 6 years ago by ncohen

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 duplicate-reverse.

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 6 years ago by ncohen

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 6 years ago by git

  • Commit changed from b2c1e310c03477183cb3e793103711989955eb57 to 55235f6a0d30333d2704303fbbeee7f8679114ec

Branch pushed to git repo; I updated commit sha1. New commits:

55235f6trac #15662 better algo and better doc

comment:8 Changed 6 years ago by ncohen

  • 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 6 years ago by git

  • Commit set to 232c4824582e31b896a820778b94ae334276129d

Branch pushed to git repo; I updated commit sha1. New commits:

b2c1e31trac #15662 implement Ihara zeta function of graphs
55235f6trac #15662 better algo and better doc
232c482trac #15662: Removing a 'if' in the algorithm

comment:10 Changed 6 years ago by git

  • Commit changed from 232c4824582e31b896a820778b94ae334276129d to 403fd968aefe0eaf3b9e72f4ec79ba8ac7d9aad5

Branch pushed to git repo; I updated commit sha1. New commits:

403fd96trac #15662 added more doc and changed name again

comment:11 Changed 6 years ago by chapoton

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/2014-51-01/S0273-0979-2013-01426-5/S0273-0979-2013-01426-5.pdf

comment:12 Changed 6 years ago by ncohen

Helloooooooooo !!

Thanks for this pointer toward the definition we use ! I tried to compare what ​http://www.ams.org/journals/bull/2014-51-01/S0273-0979-2013-01426-5/S0273-0979-2013-01426-5.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

Last edited 6 years ago by ncohen (previous) (diff)

comment:13 follow-up: Changed 6 years ago by chapoton

Maybe just a matter of factorisation ? They do not give a fully factorised form, but some ad-hoc hand-made factorisation.

comment:14 in reply to: ↑ 13 Changed 6 years ago by ncohen

Maybe just a matter of factorisation ? They do not give a fully factorised form, but some ad-hoc hand-made 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 = (1-t^2)*(1-t)*(1-2*t)*(1+t+2*t^2)^3
sage: p1 == p2
False

comment:15 follow-up: Changed 6 years ago by chapoton

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 6 years ago by ncohen

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 6 years ago by chapoton

Sorry, I guess my argument about the degree is wrong.. It is not necessarily twice the number of edges..

comment:18 Changed 6 years ago by chapoton

you forgot the power of (1-t^2) when checking the K4 result in the Bull. AMS paper:

sage: g=graphs.CompleteGraph(4)
sage: p1=g.ihara_zeta_function()
sage: p2=(1-t^2)**2*(1-t)*(1-2*t)*(1+t+2*t^2)^3
sage: p1==p2
True

comment:19 Changed 6 years ago by ncohen

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 one-line 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 follow-up: Changed 6 years ago by chapoton

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 copy-pasted the same result. This could very-well be wrong everywhere.

comment:21 in reply to: ↑ 20 Changed 6 years ago by ncohen

  • 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 copy-pasted the same result. This could very-well 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 6 years ago by chapoton

Thanks for the review !

comment:23 Changed 6 years ago by vbraun

Merge conflict... please merge in 6.1.beta5 & resolve.

comment:24 Changed 6 years ago by git

  • 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:

10181d9trac #15662: Rebase on 6.1.beta5

comment:25 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

Done. It conflicted with kirchhoff_symanzik_polynomial.

Nathann

comment:26 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.