在准备开题的时候查阅硕士论文,发现了一个算法SCAN(Structural Clustering Algorithm for Networks) ,时间复杂度很好,理论上是线性的,在实际结果(论文中的结果,我写了程序还没有做实验)中也是线性的。划分结果粗略看来也还不错。
SNAP,全称Standford Network Analysis Project,是斯坦福大学提供的一个功能非常强大的开源工具。SNAP官网
伪代码 SCAN论文及我的代码实现不好意思,因为我也经常下资源,所以下载资源需要1分。
核心的代码贴到下面,没有分数的童鞋可以自己调整一下,应该难度不大:
//记录当前的类标号 int CurClusterNum = 0; /* *对于节点遍历 *定义一下节点值的含义: *0代表为分类;大于0的代表类的标号;-1代表 non-member; -2代表队hub; -3代表outlier */ for (TNodeEDatNet<TInt, TInt>::TNodeI NI = net->BegNI(); NI < net->EndNI(); NI++) { if (net->GetNDat(NI.GetId()) <= 0) { TIntV community; //Q中存储的是节点id std::vector<int> Q; if (staticScan::IsCore(net, NI, u, e)) { CurClusterNum++; net->SetNDat(NI.GetId(), CurClusterNum); community.Add(NI.GetId()); for (int i = 0; i < NI.GetDeg(); i++) { Q.push_back(NI.GetNbrNId(i)); } while (Q.size() != 0) { //取出Q列表中的最后一个元素 TNodeEDatNet<TInt, TInt>::TNodeI NodeI = net->GetNI(Q[Q.size() - 1]); Q.pop_back(); if (IsCore(net, NodeI, u, e)) { //遍历R for (int j = 0; j < NodeI.GetDeg(); j++) { int Nid = NodeI.GetNbrNId(j); if (net->GetNI(Nid).GetDat() <= 0) { net->SetNDat(Nid, CurClusterNum); community.Add(Nid); } else if (net->GetNI(Nid).GetDat() == 0) { Q.push_back(Nid); } } } else { net->SetNDat(NodeI.GetId(), -1); } } Communities.Add(community); } else { //不是核心节点标记为non-member net->SetNDat(NI.GetId(), -1); } } } TIntV Hub, Outlier; //对于non-member节点进行判断,区别出hub和outlier for (TNodeEDatNet<TInt, TInt>::TNodeI NI = net->BegNI(); NI < net->EndNI(); NI++) { if (NI.GetDat() == -1) { int flag = -1; for (int i = 0; i < NI.GetDeg(); i++) { if (NI.GetNbrNDat(i) != flag && flag > 0 && NI.GetNbrNDat(i) > 0) { flag = -2; } flag = NI.GetNbrNDat(i); } if (flag == -2) { net->SetNDat(NI.GetId(), -2); Hub.Add(NI.GetId()); } else { net->SetNDat(NI.GetId(), -3); Outlier.Add(NI.GetId()); } } } Communities.Add(Hub); Communities.Add(Outlier); //显示聚类结果 for (int i = 0; i < Communities.Len(); i++) { for (int j = 0; j < Communities[i].Len(); j++) { std::cout<<Communities[i][j]<<"\t"; } std::cout<<std::endl; } double staticScan::ComputeSim(TNodeEDatNet<TInt, TInt>::TNodeI NodeI, TNodeEDatNet<TInt, TInt>::TNodeI NodeJ) { int ni = NodeI.GetDeg() + 1; int nj = NodeJ.GetDeg() + 1; int count = 0; for (int i = 0; i < NodeI.GetDeg(); i++) { for (int j = 0; j < NodeJ.GetDeg(); j++) { if (NodeI.GetNbrNId(i) == NodeJ.GetNbrNId(j)) { count++; } } } return (2 + count)/sqrt((double)ni)*sqrt((double)nj); } bool staticScan::IsCore(const Net& net, TNodeEDatNet<TInt, TInt>::TNodeI NodeI, int u, double e){ int Count = 0; for (int i = 0; i < NodeI.GetDeg(); i++) { //获取到邻居节点 TNodeEDatNet<TInt, TInt>::TNodeI NeighborNode = net->GetNI(NodeI.GetNbrNId(i)); double Sim = staticScan::ComputeSim(NodeI, NeighborNode); // net->SetEDat(NeighborNode.GetId(), NodeI.GetId(), Sim); // net->SetEDat(NodeI.GetId(), NeighborNode.GetId(), Sim); if (Sim > e) { Count++; } } if (Count > u) { return true; } else { return false; } }