1

I want to find the most representative nodes in each module in a modular network. I have used the Louvain algorithm on my graph and found two main modules. Now I want to know what nodes are the most infuential in this structure. e.g. nodes that are connected other nodes in the same module rather than to nodes in the other module.

Is there any node-level quantity based on the structure to represent this concept?

BenP
  • 191
  • 1
  • 15
saghi
  • 13
  • 3
  • Did my answer help? It may also be worth comparing the important nodes in the graph and in each sub-graph. – BenP Apr 04 '19 at 11:14

2 Answers2

0

Sure. Separate your graph so that you have two separate sub-graphs, one for each module you have found. Now, you could use a variety of metrics to measure the most “important” node for node-node connections in these sub-graphs. The metric that springs to mind based on your description is betweeness centrality that measures the number of shortest paths that traverse each node. Nodes with a high number of shortest paths are more important in terms of connectivity. Of course there are other measures depending on what you really want to measure including: weighted degree, page rank, and hubs.

BenP
  • 191
  • 1
  • 15
  • Thanks! but I think one problem in doing this is that it doesn't capture between and within modules edges. that is if a node has many edges to the other module as well as within module that node doesn't play that much a role in the modular structure. – saghi Apr 04 '19 at 15:46
  • I'm not sure I understand as your question was regarding the most influential node per module "I want to find the most representative nodes in each module in a modular network". Not in the network as a whole too. I think that if you apply your community detection, and then identify the node per community that has the greatest betweeness centrality that should give you a reasonable approximation of the most important nodes regarding the modular structure. – BenP Apr 04 '19 at 20:04
0

I take it that by "most influential" you mean "the node that most contributes to the overall connectivity" of the module. There isn't a single topological parameter that summarizes all the information about a node in a single number.

1) If your module is moderately to densely connected, you could measure how many (or what %) of edges are lost if you remove a node. The larger the % of edges lost, the more important the node.

2) If your module is not very densely connected (I'm thinking about linear- or tree-looking networks), another method is counting in how many submodules a module is fragmented after removing the node. The larger the number of fragments, the more important the node is for keeping the whole structure together.

Daniel A
  • 9
  • 2