How can I evaluate the connectedness of my nodes?

Posted by Travis Leleu on Stack Overflow See other posts from Stack Overflow or by Travis Leleu
Published on 2011-01-06T18:50:25Z Indexed on 2011/01/06 18:53 UTC
Read the original article Hit count: 240

Filed under:
|
|

I've got a space that has nodes that are all interconnected, based on a "similarity score". I would like to determine how "connected" a node is with the others.

My purpose is to find nodes that are poorly connected to make sure that the backlink from the other node is prioritized.

Perhaps an example would help.

I've got a web page that links to my other pages based on a similarity score. Suppose I have the pages: A, B, C, ...

A has a backlink from every other page, so it's very well connected. It also has links to all my other pages (each line in the graph is essentially bidirectional). B only has 1 backlink, from A. C has a link from A and D.

I would like to make sure that the A->B link is prioritized over the A->C link (even if the similarity score between C and A is higher than B and A).

In short, I would like to evaluate which nodes are least and best connected, so that I can mangle the results to my means.

I believe this is Graph Connectedness, but I'm at a loss to develop a (simple) algorithm that will help me here. Simply counting the backlinks to a node may be a starting point -- but then how do I take the next step, which is to properly weight the links on the original node (A, in the example above)?

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about math