Is counting the frequency a vertex appears in paths between all vertexes a valid way to determine "centrality"?

Question

I have a blog with 15+ years of posts. There are over 7,000 of them. (It's Gadgetopia, if you're curious.) I'm auditing it in preparation for a big purge, and I'm accumulating some metrics so I can "score" posts for retention or not.

One of the metrics I'm interested in is what I'm calling "link centrality."

I linked between posts a lot over the years. The posts are weaved into each other – one post will link to another, which will link to three more, which each link to five more, at least one of which links back to the first post, etc. I have a database table that tracks the links between posts. I have a scheduled job and parses each post, and pulls all the intra-site links out, and enters a record for each one. We'll call this the "link table." The link table has two columns – source and target – so it only tracks one “hop." The link table can tell me that post #1234 linked to post #5678. And another record in the table might tell me that post #5678 linked to post #9012. And so on. In this sense, every link from one post to another starts a "chain" or "path" of links.

I got to wondering how to determine what posts were most central in these chains, so I got in my head that I would use the data in the link table to set up a network map of these relationships, and run some metrics on them.

My methodology, using QuickGraph:

• I created a vertex for each distinct post that appeared in either column of the link table (as either a source or a target). I figured that any post appearing in this table was a node on the map. And, if a post didn't appear in this table, then, by definition, it wasn't a part of any path (it was orphaned/isolated from all other posts on the site).
• I created a directed edge for each link from one post to another post.
• For each combination of posts/vertices in the map (approx. 1.6 million combinations), I computed the shortest possible path between them. Note that some came up null, because there was no path.
• I iterated the edges/links of all these paths and recorded the destination vertex/post for each.
• I counted those vertices/posts up to determine what I hope to believe is some measure of "link centrality."

The theory in my head was this: if you're moving between two posts on the site that are part of the link graph – meaning they're somehow "plugged into" other posts – then the posts you "run over" the most on all these paths are probably pretty important.

One post in particular, for example, appears about 1,600 times in paths between linked posts. This post is certainly foundational to the site (it's this one) – I linked to it from many posts over the years, and those linking posts were also full of links to other posts. Additionally, its sheer age (circa 2007) make it more likely to appear in more paths.

My question

Have I accomplished anything here that I couldn't have accomplished my just counting inbound and outbound links from my link table?

Answer 1

There is an entire armada of centrality measures for networks. The one you reïnvented (unless I am misunderstanding something) is called the betweenness centrality. The number of outgoing or ingoing links is called degree.

Which centrality is better suited for you depends a lot on your question and data, and even for a given scenario, there is no clear way to say which centrality is best. On the other hand, for many centralities will arrive at the same most important nodes for many networks, so it does not really matter which one you choose.

However, as your goal is not exactly finding the most important nodes, but pruning least important ones, many centrality measures and details thereof are irrelevant for you. Also, you have the problem that pruning changes your network and thus many centrality measures.

Instead, I would probably follow an iterative approach and remove nodes that fail to meet some minimal relevance criteria, which do not improve through pruning, for example:

• Remove nodes without any link pointing to them (zero in-degree). By contrast, you probably do not want to remove nodes whose only connection to the rest of the network is a link from a very important node to them.
• Remove small clusters of posts that have no ingoing connections from the rest of the network.
• Remove (most of) long one-way “culs-de-sac”, i.e., outgoing chains of nodes looking like this: •→•→•→•→•→•→• (with the last node having no outgoing links at all).

Of course, what your criteria are strongly depends on what you wish to achieve and how much content you wish to get rid off.