Zac*_*ham 7 c++ java algorithm modularity
我正在尝试用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,MEJ Newman,C.Moore,2004公共类CNMMCommunityMetric实现CommunityMetric {私有静态类DoubleIntInt实现Comparable {public double 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对的单个对象.
所以这是原始论文,一篇文章很简单,有六页,其中只有两页是关于设计和实现的.这是一个悬崖:
Q时,分的是边缘的数量的比例内,以边的数量每个社区之间的每个社区,减去比你会从一个完全随机的期待划分.i和j一个分区,然后他们定义deltaQ_ij了如果社区i和j合并,分区的模块化将会改变多少.所以,如果deltaQ_ij > 0,合并i以及j将改善该分区的模块.deltaQ_ij每对社区.无论哪个社区i, j拥有最大的社区,都deltaQ_ij将这两个社区合并.重复.deltaQ_ij全部转为否定时,你将获得最大的模块性,但在论文中,作者让算法运行,直到只剩下一个社区.这几乎是理解算法的原因.详细信息包括如何deltaQ_ij快速计算和有效存储信息.
编辑:数据结构时间!
首先,我认为您引用的实现方式与文章的方式不同.我不太确定如何,因为代码是不可穿透的,但似乎使用union-find和hashsets代替作者的二叉树和多个堆.不知道为什么他们以不同的方式做到这一点.您可能希望通过电子邮件发送撰写该文章的人并提出要求.
总之,在算法纸需要几样东西从格式deltaQ存储在:
dQ.deltaQ_ik和deltaQ_ki固定的i.deltaQ_kj和deltaQ_jk固定j.作者提出的解决方案如下:
i,每个非零 deltaQ_ik都存储在一个平衡的二叉树中,索引为k(因此可以很容易地找到元素),并且在堆中(因此可以轻松找到该社区的最大值).deltaQ_ik每个社区i的堆中的最大值存储在另一个堆中,以便可以轻松找到总体最大值.当社区i与社区合并时j,二叉树会发生以下几件事:
i社区的每个元素都被添加到j社区的二叉树中.如果k已存在具有相同索引的元素,则将旧值和新值相加.j社区二叉树中所有剩余的"旧"值,以反映该j社区刚刚增加的事实.k,我们更新任何deltaQ_kj.i被扔掉了.同样地,堆必须发生几件事情:
i被扔掉了.j使用社区平衡二叉树中的元素从头开始重建社区堆.k的堆,deltaQ_kj更新条目的位置.i在整个堆中的条目被丢弃(导致冒泡)以及社区j和每个社区的条目k连接i或j更新.奇怪的是,当两个社区合并时,论文中没有提及deltaQ_ki从k社区的堆或树中删除值.我认为这可能是通过设置处理的a_i = 0,但我不太了解算法以确定.
编辑:尝试破译您链接的实现.他们的主要数据结构是
CmtyIdUF,一个联合查找结构,可以跟踪哪个节点在哪个社区中(文章中忽略了这一点,但除非你想从合并的痕迹中重建社区成员资格,否则似乎是必要的),MxQHeap,一堆来跟踪哪个deltaQ_ij是最大的整体.奇怪的是,当他们更新TFltIntIntTr堆中a的值时,他们不会要求堆重新堆积自己.这令人担忧.它是自动执行还是其他操作？CmtyQH,一个将社区ID映射i到一个结构的哈希映射,该结构TCmtyDat保存了deltaQ_ik该社区的堆栈.我认为.奇怪的是,虽然,所述UpdateMaxQ的的TCmtyDat结构采用线性时间,从而避免需要任何堆.更重要的是,UpdateMaxQ只有在删除堆的元素时才会调用该方法.当更新堆中任何元素的值时,它也应该被调用.| 归档时间： |
|
| 查看次数： |
3265 次 |
| 最近记录： |