public ApacheMatrix(int rowDimension, int columnDimension, boolean sparse) { if (sparse) { this.matrix = new OpenMapRealMatrix(rowDimension, columnDimension); } else { this.matrix = new Array2DRowRealMatrix(rowDimension, columnDimension); } }
public SVDAlgorithmWrapper(List<SparseWeightableVector> matrix) { int n = matrix.size(); int d = matrix.get(0).getDimension(); final OpenMapRealMatrix realMatrix = new OpenMapRealMatrix(n, d); int idx = 0; for (SparseWeightableVector vector : matrix) { realMatrix.setRowVector(idx++, vector); } this.svd = new SingularValueDecomposition(realMatrix); }
public RealMatrix toMatrix() { int n = max() + 1; RealMatrix m = new OpenMapRealMatrix(n, n); for (Entry<DiEdge, Double> entry : weights.entrySet()) { DiEdge e = entry.getKey(); double w = entry.getValue(); m.setEntry(e.get1(), e.get2(), w); } return m; }
/** * The main algorithm, returns the maximum modularity as a double * * @return */ public double findGlobalMaximumModularity() { //Store the community of each vertex as an integer HashMap<MyVertex, Integer> communityMap = new HashMap<>(); //Generate a sparse Matrix of communities - since in the beginning, every vertex has its own community, //we create it as an |V|x|V| matrix OpenMapRealMatrix sparse_Q_ij_Matrix = new OpenMapRealMatrix(filteredGraph.getVertexCount(), filteredGraph.getVertexCount()); //We also want to store each row of the matrix as a priority queue (which is almost the same thing as a heap) //We store all of these queues in a map HashMap<Integer, PriorityQueue<Pair<Integer, Double>>> rowsMap = new HashMap<>(); //Generate array for elements a_i double[] a_i_array = new double[filteredGraph.getVertexCount()]; //Set initial values for the matrix, the priority Queues, the array and the community map as described in Equation (8) and (9) initializeModularityAlgorithmParameters(sparse_Q_ij_Matrix, rowsMap, a_i_array, communityMap); //We also want another priority queue that contains the largest element of each row PriorityQueue<Pair<Integer, Pair<Integer, Double>>> maxQueue = new PriorityQueue<>((o1, o2) -> { double value1 = o1.getValue().getValue(); double value2 = o2.getValue().getValue(); return Double.compare(value2, value1); }); for (Map.Entry<Integer, PriorityQueue<Pair<Integer, Double>>> entry : rowsMap.entrySet()) { maxQueue.add(new Pair<>(entry.getKey(), entry.getValue().peek())); } //Now the actual algorithm begins int numberOfCommunities = filteredGraph.getVertexCount(); double maxModularity = 0; //Repeat until only one community is left while (numberOfCommunities > 1) { //Retrieve largest entry Pair<Integer, Pair<Integer, Double>> largestEntry = maxQueue.poll(); //Join the communities joinCommunities(largestEntry.getKey(), largestEntry.getValue().getKey(), communityMap); //Update the sparse matrix, the priority queues and a[i] updateParameters(sparse_Q_ij_Matrix, rowsMap, maxQueue, a_i_array, largestEntry.getKey(), largestEntry.getValue().getKey(), communityMap); //Update maximal modularity (Remember: This is the value we actually want to calculate!) maxModularity += largestEntry.getValue().getValue(); //Decrement community counter by 1 numberOfCommunities--; } //Modularity is now maximized return maxModularity; }
/** * Initializes the values of the given parameters * * @param sparse_Q_ij_Matrix * @param rowsMap * @param a_i_array * @param communityMap */ private void initializeModularityAlgorithmParameters(OpenMapRealMatrix sparse_Q_ij_Matrix, HashMap<Integer, PriorityQueue<Pair<Integer, Double>>> rowsMap, double[] a_i_array, HashMap<MyVertex, Integer> communityMap) { //Both of these measures will be needed below double m = filteredGraph.getEdgeCount(); HashMap<TaxonNode, Integer> nodeDegrees = getNodeDegrees(); //Initialize community map //Initially, every vertex has its own community int communityCounter = 0; for (MyVertex vertex : filteredGraph.getVertices()) { communityMap.put(vertex, communityCounter); communityCounter++; } //Define a comparator for the priority queues Comparator<Pair<Integer, Double>> myComparator = (o1, o2) -> Double.compare(o2.getValue(), o1.getValue()); //In these loops, the initial values for the array of a_i, the row-PriorityQueues and the sparse matrix are set for (Map.Entry<MyVertex, Integer> entry_i : communityMap.entrySet()) { a_i_array[entry_i.getValue()] = nodeDegrees.get(entry_i.getKey().getTaxonNode()) / (2 * m); PriorityQueue<Pair<Integer, Double>> rowQueue = new PriorityQueue<>(myComparator); for (Map.Entry<MyVertex, Integer> entry_j : communityMap.entrySet()) { double q_value; if (filteredGraph.findEdge(entry_i.getKey(), entry_j.getKey()) != null) { q_value = 1 / (2 * m) - (nodeDegrees.get(entry_i.getKey().getTaxonNode()) * nodeDegrees.get(entry_j.getKey().getTaxonNode())) / Math.pow(2 * m, 2); } else q_value = 0; sparse_Q_ij_Matrix.setEntry(entry_i.getValue(), entry_j.getValue(), q_value); rowQueue.add(new Pair<>(entry_j.getValue(), q_value)); } rowsMap.put(entry_i.getValue(), rowQueue); } }
/** * Updates the given parameters based on the two merged communities * * @param sparse_Q_ij_Matrix * @param rowsMap * @param maxQueue * @param a_i_array * @param i * @param j * @param communityMap */ private void updateParameters(OpenMapRealMatrix sparse_Q_ij_Matrix, HashMap<Integer, PriorityQueue<Pair<Integer, Double>>> rowsMap, PriorityQueue<Pair<Integer, Pair<Integer, Double>>> maxQueue, double[] a_i_array, int i, int j, HashMap<MyVertex, Integer> communityMap) { //First, update the matrix // 1. Make sure j is smaller than i, swap if necessary if (j > i) { int tmp = j; j = i; i = tmp; } // 2. Update j's row and column and set i's row and column to -MAXVALUE for (int k = 0; k < sparse_Q_ij_Matrix.getColumnDimension(); k++) { //Check if k is still a valid community identifier if (sparse_Q_ij_Matrix.getEntry(k, k) == -2) continue; //Check if k is connected to both i and j or only to one of them double firstSummand, secondSummand; if (sparse_Q_ij_Matrix.getEntry(i, k) == 0) firstSummand = -2 * a_i_array[i] * a_i_array[k]; else firstSummand = sparse_Q_ij_Matrix.getEntry(i, k); if (sparse_Q_ij_Matrix.getEntry(j, k) == 0) secondSummand = -2 * a_i_array[j] * a_i_array[k]; else secondSummand = sparse_Q_ij_Matrix.getEntry(j, k); //Set Q(j,k) and Q(k,j) to the sum of these two sparse_Q_ij_Matrix.setEntry(j, k, firstSummand + secondSummand); sparse_Q_ij_Matrix.setEntry(k, j, firstSummand + secondSummand); //Set Q(i,k) and Q(k,i) to -2 so that they're ignored from now on sparse_Q_ij_Matrix.setEntry(i, k, -2); sparse_Q_ij_Matrix.setEntry(k, i, -2); } //Update row queues Comparator<Pair<Integer, Double>> myComparator = (o1, o2) -> Double.compare(o2.getValue(), o1.getValue()); for (int index_i = 0; index_i < sparse_Q_ij_Matrix.getRowDimension(); index_i++) { if (sparse_Q_ij_Matrix.getEntry(index_i, 0) == -2) continue; PriorityQueue<Pair<Integer, Double>> rowQueue = new PriorityQueue<>(myComparator); for (int index_j = 0; index_j < sparse_Q_ij_Matrix.getColumnDimension(); index_j++) { if (sparse_Q_ij_Matrix.getEntry(index_i, index_j) == -2) continue; rowQueue.add(new Pair<>(index_j, sparse_Q_ij_Matrix.getEntry(index_i, index_j))); } rowsMap.put(index_i, rowQueue); } //Update maxQueue maxQueue.clear(); for (Map.Entry<Integer, PriorityQueue<Pair<Integer, Double>>> entry : rowsMap.entrySet()) { maxQueue.add(new Pair<>(entry.getKey(), entry.getValue().peek())); } //Update a_i_array for (int index = 0; index < a_i_array.length; index++) { if (sparse_Q_ij_Matrix.getEntry(index, 0) != -2) a_i_array[index] = calcA_i(index, communityMap); } }
@Override public List<SparseWeightableVector> takeSample(List<SparseWeightableVector> pointset) { if (size >= pointset.size()) return pointset; int d = pointset.get(0).getDimension(); final OpenMapRealMatrix A = new OpenMapRealMatrix(pointset.size(), d); int idx = 0; // Create block matrix so SVD algorithm will be able to work with it. for (SparseWeightableVector each : pointset) { A.setRowVector(idx++, each.getVector()); } SingularValueDecomposition svd = new SingularValueDecomposition(A); final RealMatrix S = svd.getS().getSubMatrix(0, size, 0, size); final RealMatrix VT = svd.getV().getSubMatrix(0, d - 1, 0, size).transpose(); // If point set is just a concat of two or more data chunks, need to // go over all points and collect distinct weights values, then to sum // everything into a new weight. double totalWeight = 0; Set<Double> weights = Sets.newHashSet(); for (SparseWeightableVector vector : pointset) { weights.add(vector.getWeight()); } for (Double weight : weights) { totalWeight += weight; } // If totalWeight is zero that means no one actually computed weights for these points, // hence they are new, therefore totalWeight computed according to the formula. if (totalWeight == 0) totalWeight = Math.pow(A.getFrobeniusNorm(), 2) - Math.pow(S.getFrobeniusNorm(), 2); // Get the coreset. final RealMatrix C = S.multiply(VT); // Copy into final list. final List<SparseWeightableVector> results = Lists.newArrayList(); for (int i = 0; i < C.getRowDimension(); ++i) { results.add(new SparseWeightableVector(C.getRow(i), totalWeight)); } return results; }
