A Neighborhood-Inflated Seed Expansion with Spread Hubs C++ implementation

A C++ implementation of the Neighborhood-Inflated Seed Expansion with Spread Hubs method (NISE-SPH) [1] algorithm. The NISE-SPH is an overlapping community detection algorithm proposed by Whang, Gleich and Dhillon (2019) [1].

Since I am not a NISE-SPH author, I tried to made this implementation as close as possible to the algorithm description provided by the authors in [1].

Disclaimer

Note that I am not a NISE-SPH author, so this NISE-SPH version may has errors and/or discrepancies with the actual Whang, Gleich and Dhillon [1] NISE-SPH algorithm.

Prerequisites

• GNU Make

• gcc 4.8 compiler or an early version.

Compile and run instructions

Go to the nise-sph folder and to compile type:

$ make

To run execute the lecm file:

$ ./nise_sph [flag] <value>

The flags are the parameters of the NISE-SPH algorithm (see [1] for a full description of each algorithm parameter):

flag	description
-f	input graph path
-s	number of seeds
-a	alpha value
-e	epsilon value

-f and -s must to be specified. For the remaining flags, the algorithm can use default values following values defined by [1]:

a = 0.99 and e = 1e-4.

NISE-SPH algorithm reads file containing the graph's list of edges. In this file, edges are increasing ordered considering the source vertex and they are repeated even if the graph is undirected. In addition, the first file entry has the number of vertices. For example:

4
1	2
1	4
2	1
2	3
3	2
4	1

The example above represents an undirected graph with four vertices and three edges (1, 2), (1, 4) and (2, 3).

After execution, is produced a file clustering.dat. This file contains the clustering generated by NISE-SPH following the structure below:

0 2 5
1
3 6 7 4

Means that the clustering has three clusters where each row represents a cluster and its memberships. In the example above, the clustering has three clusters in which vertices 0, 2 and 5 are contained in the first cluster, vertex 1 belongs to the second one and vertices 3, 6, 7 and 4 are contained in the third cluster.

Example:

$ ./nise_sph -f ./example/network_1000_7327.lfi -s 200 -a 0.99 -e 1e-4

License

This project is licensed under the GNU General Public License - see the LICENSE.md file for details.

References

[1] J. J. Whang, D. F. Gleich and I. S. Dhillon. Overlapping community detection using neighborhood-inflated seed expansion, IEEE Transactions on Knowledge and Data Engineering 28(5) (2016) p. 1272-1284.