Kpath Network Centrality

Emilio Ferrara (Professor of Computer Science at USC) & (HUmans | MAchines | Networks | Society) Lab


WERW-Kpath (Weighted Edge Random Walks – K Path) is a fast algorithm to weight edges in complex networks exploiting global topological features adopting Simple Random Walks of bounded length (up to K).

The strategy relies on three steps:

  1. initial weight assignment;
  2. message propagation simulations on the network exploiting Simple Random Walks of fixed length up to K;
  3. final weight computation.

WERW-Kpath is computationally efficient since its cost is near linear with respect to the number of edges in the network.

You can also use WERW-Kpath to weight a network and then running an optimized community detection algorithm such as CONCLUDE to enhance performance and quality of results.

The only condition of use of this algorithm is the following:

  • The corresponding papers are cited

Related Papers

The following papers are all related to WERW-Kpath.
Please cite those which are relevant to your purposes if you use WERW-Kpath.

Download WERW-Kpath

You can download an early version of WERW-Kpath from HERE.

The package contains the following user guide.

USER GUIDE
**********

To launch the WERW-Kpath algorithm type:

  • java -jar werw-kpath.jar input-filename output-filename k-path-length delimiter(default: tab-separated-value)
input-filename: the name of the file containing the edgelist representing the network output-filename: the output filename k-path-length: the length of the k-path random walk (reasonable values range in the interval [5, 20]) delimiter: this parameter is optional, default "\t" (tab-separated values); example of other options: "," (csv) or " " (space-separated values) Example line commands:
  • java -jar werw-kpath.jar facebook-links.txt weighted-facebook-links.txt 10
This call will invoke WERW-Kpath passing the input network file called facebook-links.txt, prepared as an edgelist of tab-separated values, exploiting k-path random walks up to length 10.
  • java -Xmx4G -jar werw-kpath.jar facebook-links.txt weighted-facebook-links.txt 10
This call will invoke WERW-Kpath asking the Java Virtual Machine to allocate 4G of memory to this process. This parameter is possibly required when managing large networks (millions of edges).
  • java -Xmx4G -jar werw-kpath.jar facebook-links.txt weighted-facebook-links.txt " " 10
This invokation is required for passing a "space-separated" edgelist. REFERENCE ********* If you use this algorithm please cite the following papers: P De Meo, E Ferrara, G Fiumara and A Ricciardello. A novel measure of edge centrality in social networks. Knowledge-based Systems, 30:136-150, 2012 P De Meo, E Ferrara, G Fiumara, and A Provetti. Enhancing community detection using a network weighting strategy. Information Sciences, 222:648-668, 2013 P De Meo, E Ferrara, G Fiumara, and A Provetti. Mixing local and global information for community detection in large networks. Journal of Computer and System Sciences 80(1):72-87, 2014

Visit the 2024 Election Integrity Online initiative | Visit REGULARITY AI for Consultancy & Expert Witness Services