Kpath Network Centrality

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.

• A novel measure of edge centrality in social networks.
  P De Meo, E Ferrara, G Fiumara and A Ricciardello.
  Knowledge-based Systems, 30:136-150, 2012
  PDF | Journal page

• Enhancing community detection using a network weighting strategy.
  P De Meo, E Ferrara, G Fiumara, and A Provetti.
  Information Sciences, 222:648-668, 2013
  PDF | Journal page

• Mixing local and global information for community detection in large networks.
  P De Meo, E Ferrara, G Fiumara, and A Provetti.
  Journal of Computer and System Sciences, 80(1):72-87, 2014
  PDF | Journal page

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