I am working through the textbook "Graph-Based Natural Language Processing and Information Retrieval", where I've got a question on implementation of this first Latex looking formula/algorithm.

Can you help me turn the formula under 1.2 Graph Properties into python code? Yes, I know there are many other languages, but python is more user-friendly so I'm starting there, and will eventually rewrite it into C.

As I read the above node example, sorry the D and E nodes were cut off. Node A has two outflowing arrows notating it as their head node, and it is the one tail node.

This first sentence references the Graphs: To traverse from A to B, If A to B value is sufficient (above Nx), go to B. If A to B value is below Nx, go A to C to D to A to B total cost is 5.2+7+1+8 = 21.20 traverse cost, this makes sense.

enter image description here

This sentence refers to the Latex formula in the book. Then to start the formula calculation, the average degree of a graph "a" is equal to the sum of, one over N, times the sum of the in-degree of vertices? Asserting that the sum is a non zero integer between 1 and N?

Ok, I only loaded one page and hope that's not a TOS violation or causes issue, it's a challenge to find people who understand graph theory.

Let me know what questions you have, but I'm just wanting to get clarification if my understanding is what this page is saying.

  • $\begingroup$ Please, can you be more specific about the sentences you're referring to? Don't just post the screenshot. Only copy and paste the relevant sentences and remove as many unnecessary details as possible. This question has been flagged as unclear, so please try to clarify it further! $\endgroup$
    – nbro
    Mar 9, 2020 at 16:18
  • $\begingroup$ Sure, I'm just trying to understand what the a=1/N algorithm means in the screenshot. For example, a sentence would be "a equals one over N times the sum of degree Vi, where Vi is a non zero integer from one to n"? $\endgroup$ Mar 12, 2020 at 20:01

1 Answer 1


Each node is a position in the arrays

  • values = value of the node

  • conn = indexes of connected nodes

If its an undirected graph, each node must have all the nodes to which they are attached. Instead, in directed graphs, only the start node has the index. For your image:

values = ['A','B','C','D','E']
conn = [[1,2,3],[0,4],[0,3,4],[0,2,3],[1,3]]

Example = 'A' -> 1 ('B') ,2 ('C') ,3 ('D')

def averageGraph(conn):
    if conn.all() != None:
        average = 0
        for node in conn:
            average = average + len(node) #len(node) = nº nodes connected = degree
        return average / len(conn)
        return None
  • $\begingroup$ Thank you Alejandro, that is very helpful! What is your background if you don’t mind me asking as I have a few hundred pages to go through similar to this one. $\endgroup$ Apr 3, 2020 at 2:26
  • $\begingroup$ The Maths are knowledge that you learn at university, but any PDF of introduction to graph theory can explain you very well, as soon as you understand a little they are very simple concepts! Good luck $\endgroup$ Apr 4, 2020 at 10:12

Not the answer you're looking for? Browse other questions tagged .