README This file describes (briefly) how to use the code for the paper "Modularity-Maximizing Communities via Mathematical Programming". The code and README were written by Gaurav Agarwal. In case of questions, Gaurav can be reached by e-mail at the address that is obtained by removing the letter 'q' in all places from the following address: qgauqravqagarqwaql4@qgmaqil.cqoqm --------- Converting the data to adjaceny matrix ---------- Helper class Pajek2Adj.java can be used to convert a pajek(.net) file to adjaceny matrix format Usage: Pajek2Adj ---------LP Based Clustering --------- Requirements: CPLEX, Java File Name Abbreviations: pajek (net) file : The input file in pajek format. adj_mat_file : The network representation in adjancey matrix format. Each entry is 0/1 representing absence/presence of an edge. dist_mat_file : This is an intermediate file containg LP computed distances. op_cluster_file : File containing final clustering. Each row represents one cluster and entries in the row represent nodes belonging to the cluster. Step 1: Solving the LP using CPLEX software on the adjacency matrix representation of the graph. 1. Compile the file SymMinDisAgreeLP.cpp using cplex libraries. 2. Run the LP binary using the following command Usage: SymMinDisAgreeLP 3. The output file from step 2 will be used as input for the next step of rounding the LP. Step 2: Rounding the LP assignment Use the Cluster.java program to round the LP Usage: Cluster Control flags in Cluster.java: The following variables control how the next unused point should be selected in the rounding algorithm private static boolean RANDOMNESS_ON = false; // If true, select the next point randomly else use the following variables to pick the next point. private static boolean SmallestClusterFirst; // Select the node leading to the smallest cluster private static boolean BiggestClusterFirst; // Select the node leading to largest cluster The variable num_tries controls how many iterations of the rounding algorithm to run. --------- QP Based Clustering --------- Requirements: Csdp, Matlab, Java Steps: 1. Compile the java files Node.java and Dendogram.java and put the class files in Matlab's javaclasspath http://www.mathworks.com/help/matlab/matlab_external/bringing-java-classes-and-methods-into-matlab-workspace.html 2. Install Csdp solver and the matlab interface and ensure that csdp is callable from matlab http://euler.nmt.edu/~brian/csdpuser.pdf 3. Call the matlab method progressive_sdp_cluster.m with as parameters. This will invoke CSDP and java class files internally to produce the final output. The variable max_tries=5000; in the filesdp_cluster can be tweaked in order to decide the maximum number of random planes to use for cutting the Hyper Sphere.