Problem of finding corrupted cliques is formulated as follows: to find minimal number of edge additions and removals to convert graph into a set of cliques. Search for corrupted cliques (or dense subgraphs) of some graph is a very common problem arising in bioinformatics (e.g., co-expression of genes) and studies of social interactions (e.g., recommendation services). DSF tool takes as an input indirected graph in GRAPH format and outputs decomposition where the identical ids are assigned for vertices from the same dense subgraph. Density of subgraph on N vertices and M edges is computed as ratio of M to maximal possible number of edges (N * (N - 1) / 2) and can be tuned by user.
./dense_subgraph_finder.py --test
If the installation is successful, you will find the following information at the end of the log:
Thank you for using Dense Subgraph Finder!
Log was written to <dsf_installation_dir>/dsf_test/dense_subgraph_finder.log
DSF takes as an input indirected (weighted or unweighted) graph in GRAPH format and constructs dense subgraph decomposition.
To run DSF, type:
./dense_subgraph_finder.py [options] -g <input.graph> -o <output_dir>
-g <input.graph>-o / --output <output_dir>-t/--threads <int>16.
--test
./dense_subgraph_finder.py -g test_dataset/test.graph -o dsf_test
--help-f / --min-fillin <float>0.6.
-s / --min-size <int>min-size will be decomposed trivially (all vertices are in the same dense subgraph).
Default value is 5.
-n / --min-snode-size <int>5.
--save-aux-filesinput.graph with
minimal edge fill-in value 0.9, type:
./dense_subgraph_finder.py -g input.graph -f 0.9 -o dsf_test
-o)
and outputs the following files there:
|
|
|
||
|
7 9 2 3 1 3 1 2 4 6 7 3 6 7 3 4 7 3 4 6 |
7 9 001 2 20 3 -3 1 20 3 4.5 1 -3 2 4.5 4 1 6 0.7 7 0.8 3 1 6 -1.5 7 43 3 0.7 4 -1.5 7 7.8 3 0.8 4 43 6 7.8 |
7 9 011 3 2 20 3 -3 7 1 20 3 4.5 2 1 -3 2 4.5 4 1 6 0.7 7 0.8 0.6 3 1 6 -1.5 7 43 1 1 3 0.7 4 -1.5 7 7.8 11.5 3 0.8 4 43 6 7.8 |
||
| The first line shows number of vertices (7) and number of edges (9). Each of the next lines contains vertex neighbours. E.g., the second line notes that vertex 1 is connected with vertices 2 and 3. | The first line shows number of vertices (7), number of edges (9) and description 001 that denotes edge weighted graph. Each of the next lines contains vertex neighbours and weights of corresponding edges (highlighted in blue) for graph vertices. E.g., the second line notes that vertex 1 is connected with vertex 2 by edge of weigth 20 and vertex 3 by the edge of weigth -3. | The first line shows number of vertices (7), number of edges (9) and description 011 that denotes edge & vertex weighted graph. Each of the next lines contains vertex weight (highlighed in red), its neighbours and weights of corresponding edges (highlighted in blue). E.g., the second line notes that vertex 1 of weight 3 is connected with vertex 2 by edge of weigth 20 and vertex 3 by the edge of weigth -3. |