The algorithm proposed here iterates through the boundary node set and performs a set of independent truncated random walkers originating at each boundary node, until convergence is reached in the distribution of visits to the nodes in the vicinity of each boundary node. It is the counts of the visits from the random walkers to the boundary nodes and nodes in their vicinity which allows a ranking in terms of being able to influence another community by spread of content.
The description of the algorithm is summarized in steps 1 to 4 of the outline given in
Table REF .
In the first step of the algorithm
the set of connected graphs is extracted from the original graph of the network, \(\textbf {G}\) ,
using breadth first search (BFS). There exist many efficient methods for performing BFS and in
[1]} it is shown that the step of acquiring the set of connected components
can be performed in \(\Omega \left( \text{log}N\right)\) . The second step
is to label each node according to the community it belongs to.
There is a wide selection of algorithms for obtaining the community structure, [2]}, [3]}. In our work, we use the
Louvain method of [4]}. The run time of the Louvain algorithm is
\(\Omega \left( N\text{log}N \right)\) , and there is an efficient implementation available.
Tests run with this method report working with millions of nodes under 2 minutes on a standard PC.
It is a greedy algorithm using the modularity index, [5]}, as an optimisation criteria,
which has the benefit that the number of iterations taken by the algorithm can be controlled to some extent by examining
the value of the change in the index per iteration.
The third step extracts the set of boundary nodes which control the information exchange between different communities as they are the only nodes that connect directly to nodes in a different community.
