Java — реализация обнаружения сообщества Clauset-Newman-Moore

Я пытаюсь реализовать вышеупомянутый алгоритм обнаружения сообщества в Java, и, хотя у меня есть доступ к коду C ++ и оригинальной статье, я не могу заставить его работать вообще. Моя главная проблема заключается в том, что я не понимаю назначение кода — то есть, как работает алгоритм. В практическом плане мой код застревает в бесконечном цикле mergeBestQ, список heap кажется, становится больше на каждой итерации (как и следовало ожидать от кода), но значение topQ всегда возвращает одно и то же значение.

График, на котором я тестирую, довольно большой (300 000 узлов, 650 000 ребер). Исходный код, который я использую для своей реализации, взят из библиотеки SNAP (https://github.com/snap-stanford/snap/blob/master/snap-core/cmty.cpp). Было бы замечательно, если бы кто-то мог объяснить мне интуицию алгоритма, кажется, что он изначально устанавливает каждый узел в свое собственное сообщество, а затем записывает значение модульности (независимо от того, что это) каждой пары соединенных узлов в график, затем найти пару узлов, которые имеют наибольшую модульность и переместить их в то же сообщество. Кроме того, если бы кто-то мог предоставить псевдокод среднего уровня, это было бы здорово. Здесь моя реализация до сих пор, я попытался сохранить ее в одном файле для краткости, однако CommunityGraph и CommunityNode находятся в другом месте (не требуется). Граф поддерживает список всех узлов, и каждый узел поддерживает список своих соединений с другими узлами. При запуске он никогда не выходит за черту while(this.mergeBestQ()){}

ОБНОВЛЕНИЕ — обнаружил несколько ошибок в моем коде после тщательного анализа. Теперь код ОЧЕНЬ быстро завершается, но не полностью реализует алгоритм, например, 300 000 узлов в графе, он утверждает, что существует приблизительно 299 000 сообществ (т.е. примерно 1 узел на сообщество). Я перечислил обновленный код ниже.
/// Метод обнаружения сообщества Clauset-Newman-Moore.
/// На каждом этапе объединяются два сообщества, которые вносят максимальный положительный вклад в глобальную модульность.
/// См .: Поиск структуры сообщества в очень больших сетях, A. Clauset, M.E.J. Ньюман, К. Мур, 2004
открытый класс CNMMCommunityMetric реализует CommunityMetric {
закрытый статический класс DoubleIntInt реализует Comparable {
публичный двойной val1;
public int val2;
public int val3;
DoubleIntInt (double val1, int val2, int val3) {
this.val1 = val1;
this.val2 = val2;
this.val3 = val3;
}

    @Override
public int compareTo(DoubleIntInt o) {
//int this_sum = this.val2 + this.val3;
//int oth_sum = o.val2 + o.val3;
if(this.equals(o)){
return 0;
}
else if(val1 < o.val1 || (val1 == o.val1 && val2 < o.val2) || (val1 == o.val1 && val2 == o.val2 && val3 < o.val3)){
return 1;
}
else{
return -1;
}
//return this.val1 < o.val1 ? 1 : (this.val1 > o.val1 ? -1 : this_sum - oth_sum);
}

@Override
public boolean equals(Object o){
return this.val2 == ((DoubleIntInt)o).val2 && this.val3 == ((DoubleIntInt)o).val3;
}

@Override
public int hashCode() {
int hash = 3;
hash = 79 * hash + this.val2;
hash = 79 * hash + this.val3;
return hash;
}
}

private static class CommunityData {
double DegFrac;
TIntDoubleHashMap nodeToQ = new TIntDoubleHashMap();
int maxQId;

CommunityData(){
maxQId = -1;
}

CommunityData(double nodeDegFrac, int outDeg){
DegFrac = nodeDegFrac;
maxQId = -1;
}

void addQ(int NId, double Q) {
nodeToQ.put(NId, Q);
if (maxQId == -1 || nodeToQ.get(maxQId) < Q) {
maxQId = NId;
}
}

void updateMaxQ() {
maxQId=-1;
int[] nodeIDs = nodeToQ.keys();
double maxQ = nodeToQ.get(maxQId);
for(int i = 0; i < nodeIDs.length; i++){
int id = nodeIDs[i];
if(maxQId == -1 || maxQ < nodeToQ.get(id)){
maxQId = id;
maxQ = nodeToQ.get(maxQId);
}
}
}

void delLink(int K) {
int NId=getMxQNId();
nodeToQ.remove(K);
if (NId == K) {
updateMaxQ();
}
}

int getMxQNId() {
return maxQId;
}

double getMxQ() {
return nodeToQ.get(maxQId);
}
};
private TIntObjectHashMap<CommunityData> communityData = new TIntObjectHashMap<CommunityData>();
private TreeSet<DoubleIntInt> heap = new TreeSet<DoubleIntInt>();
private HashMap<DoubleIntInt,DoubleIntInt> set = new HashMap<DoubleIntInt,DoubleIntInt>();
private double Q = 0.0;
private UnionFind uf = new UnionFind();
@Override
public double getCommunities(CommunityGraph graph) {
init(graph);
//CNMMCommunityMetric metric = new CNMMCommunityMetric();
//metric.getCommunities(graph);
// maximize modularity
while (this.mergeBestQ(graph)) {
}
// reconstruct communities
HashMap<Integer, ArrayList<Integer>> IdCmtyH = new HashMap<Integer, ArrayList<Integer>>();
Iterator<CommunityNode> ns = graph.getNodes();
int community = 0;
TIntIntHashMap communities = new TIntIntHashMap();
while(ns.hasNext()){
CommunityNode n = ns.next();
int r = uf.find(n);
if(!communities.contains(r)){
communities.put(r, community++);
}
n.setCommunity(communities.get(r));
}
System.exit(0);
return this.Q;
}

private void init(Graph graph) {
double M = 0.5/graph.getEdgesList().size();
Iterator<Node> ns = graph.getNodes();
while(ns.hasNext()){
Node n = ns.next();
uf.add(n);
int edges = n.getEdgesList().size();
if(edges == 0){
continue;
}
CommunityData dat = new CommunityData(M * edges, edges);
communityData.put(n.getId(), dat);
Iterator<Edge> es = n.getConnections();
while(es.hasNext()){
Edge e = es.next();
Node dest = e.getStart() == n ? e.getEnd() : e.getStart();
double dstMod = 2 * M * (1.0 - edges * dest.getEdgesList().size() * M);//(1 / (2 * M)) - ((n.getEdgesList().size() * dest.getEdgesList().size()) / ((2 * M) * (2 * M)));// * (1.0 - edges * dest.getEdgesList().size() * M);
dat.addQ(dest.getId(), dstMod);
}
Q += -1.0 * (edges*M) * (edges*M);
if(n.getId() < dat.getMxQNId()){
addToHeap(createEdge(dat.getMxQ(), n.getId(), dat.getMxQNId()));
}
}
}
void addToHeap(DoubleIntInt o){
heap.add(o);
}

DoubleIntInt createEdge(double val1, int val2, int val3){
DoubleIntInt n = new DoubleIntInt(val1, val2, val3);
if(set.containsKey(n)){
DoubleIntInt n1 = set.get(n);
heap.remove(n1);
if(n1.val1 < val1){
n1.val1 = val1;
}
n = n1;
}
else{
set.put(n, n);
}
return n;
}
void removeFromHeap(Collection<DoubleIntInt> col, DoubleIntInt o){
//set.remove(o);
col.remove(o);
}
DoubleIntInt findMxQEdge() {
while (true) {
if (heap.isEmpty()) {
break;
}

DoubleIntInt topQ = heap.first();
removeFromHeap(heap, topQ);
//heap.remove(topQ);
if (!communityData.containsKey(topQ.val2) || ! communityData.containsKey(topQ.val3)) {
continue;
}
if (topQ.val1 != communityData.get(topQ.val2).getMxQ() && topQ.val1 != communityData.get(topQ.val3).getMxQ()) {
continue;
}
return topQ;
}
return new DoubleIntInt(-1.0, -1, -1);
}
boolean mergeBestQ(Graph graph) {
DoubleIntInt topQ = findMxQEdge();
if (topQ.val1 <= 0.0) {
return false;
}
// joint communities
int i = topQ.val3;
int j = topQ.val2;
uf.union(i, j);

Q += topQ.val1;
CommunityData datJ = communityData.get(j);
CommunityData datI = communityData.get(i);
datI.delLink(j);
datJ.delLink(i);

int[] datJData = datJ.nodeToQ.keys();
for(int _k = 0; _k < datJData.length; _k++){
int k = datJData[_k];
CommunityData datK = communityData.get(k);
double newQ = datJ.nodeToQ.get(k);
//if(datJ.nodeToQ.containsKey(i)){
//  newQ = datJ.nodeToQ.get(i);
//}
if (datI.nodeToQ.containsKey(k)) {
newQ = newQ + datI.nodeToQ.get(k);
datK.delLink(i);
}     // K connected to I and J
else {
newQ = newQ - 2 * datI.DegFrac * datK.DegFrac;
}  // K connected to J not I
datJ.addQ(k, newQ);
datK.addQ(j, newQ);
addToHeap(createEdge(newQ, Math.min(j, k), Math.max(j, k)));
}

int[] datIData = datI.nodeToQ.keys();
for(int _k = 0; _k < datIData.length; _k++){
int k = datIData[_k];
if (!datJ.nodeToQ.containsKey(k)) { // K connected to I not J
CommunityData datK = communityData.get(k);
double newQ = datI.nodeToQ.get(k) - 2 * datJ.DegFrac * datK.DegFrac;
datJ.addQ(k, newQ);
datK.delLink(i);
datK.addQ(j, newQ);
addToHeap(createEdge(newQ, Math.min(j, k), Math.max(j, k)));
}
}
datJ.DegFrac += datI.DegFrac;
if (datJ.nodeToQ.isEmpty()) {
communityData.remove(j);
} // isolated community (done)
communityData.remove(i);
return true;
}
}

ОБНОВЛЕНИЕ: приведенный в настоящее время код является довольно быстрым и занимает половину использования памяти по сравнению с «самым быстрым» решением, но только на ~ 5% медленнее. Разница заключается в использовании hashmap + treest против очереди приоритетов и обеспечении того, чтобы в любой момент времени существовал только один объект для данной пары i, j.