參考資料：
MULE算法
不確定圖上的枚舉算法研究
Bron-Kerbosch算法視頻介紹
Bron-Kerbosch算法
MULE（Maximal Uncertain CLique Enumeration ）算法的論文原文是 Mining Maximal Cliques from an Uncertain Graph
論文作者：Arko Provo Mukherjee 监透，Pan Xu锄贷，Srikanta Tirthapura
發(fā)表時間：2015 IEEE 31st International Conference on Data Engineering
Bron-Kerbosch算法是在確定圖上找出極大團鞍历，MULE算法是在不確定圖上找出極大團。
??我們現(xiàn)在的目的疾瓮，是要在不確定圖上找出極大團，現(xiàn)有的不確定圖上極大團枚舉算法中，基于頂點編號升序的典型算法—MULE 算法性能較好，其時間復(fù)雜度為 O(n·2n)虏辫。但是MULE 算法的時間代價會隨著不確定圖頂點規(guī)模的增大而急劇上升，而隨著大數(shù)據(jù)和互聯(lián)網(wǎng)技術(shù)的發(fā)展锈拨，不確定圖的頂點規(guī)模越來越大，那么 MULE 算法也將難以滿足實際應(yīng)用的需求羹唠。
因此奕枢，通過將原圖劃分為子圖娄昆，過濾掉其中絕對不可能成為 α-極大團的頂點集合，提高算法的計算效率缝彬，從而達到優(yōu)化時間性能的目的萌焰。
算法的主要思想：
先不考慮原圖中邊上的概率，通過Bron-Kerbosch算法在原圖中谷浅，找到一個個極大團子圖扒俯。再對這每一個極大團子圖，使用MULE算法一疯，找出我們所需要的不確定圖中的極大團撼玄。
原不確定圖
??例如這是原不確定圖，在不考慮概率的情況下墩邀，我們利用Bron-Kerbosch算法可以得到5個極大團子圖掌猛，分別是{1，2眉睹，3}荔茬、{2，3竹海，5}慕蔚、{3，4斋配，5}孔飒、{5，6}许起、{6十偶，7，8园细，9}惦积。
??接下來對每一個極大團子圖調(diào)用 MULE 算法，枚舉其中的 α-極大團（這里給定α=0.1猛频，團概率大于等于0.1的就是α-極大團狮崩，團概率就是團中每條邊上權(quán)值的乘積）對于頂點集合{1，2鹿寻，3}所代表的極大團子圖睦柴，調(diào)用 MULE 算法，可得頂點集合{1毡熏，2坦敌，3}本身就是一個 α-極大團；對于頂點集合{2，3狱窘，5}所代表的極大團子圖杜顺，調(diào)用 MULE 算法，可得頂點集合{2蘸炸，3}躬络、{2，5}以及{3搭儒，5}是 α-極大團穷当；對于頂點集合{3，4淹禾，5}所代表的極大團子圖馁菜，調(diào)用 MULE 算法，可得頂點集合{3稀拐，4}火邓、{3，5}以及{4德撬，5}是 α-極大團铲咨；對于頂點集合{5，6}所代表的極大團子圖蜓洪，調(diào)用 MULE 算法纤勒，可得頂點集合{5，6}本身就是一個 α-極大團隆檀；對于頂點集合{6摇天，7，8恐仑，9}所代表的極大團子圖泉坐，調(diào)用 MULE 算法，可得頂點集合{6裳仆，7腕让，8，9}本身就是一個 α-極大團歧斟。因此纯丸，在對每一個極大團子圖調(diào)用 MULE 算法后，得到的所有 α-極大團為{1静袖，2觉鼻，3}、{2队橙，3}坠陈、{2萨惑，5}、{3仇矾，5}咒钟、{3，4}若未、{3，5}倾鲫、{4粗合，5}、{5乌昔，6}以及{6隙疚，7，8磕道，9}共計 9 個 α-極大團供屉。
??在原圖中，給定 α = 0.1溺蕉，那么不確定圖 G 中的 α-極大團分別為頂點集合{1伶丐，2，3}疯特、{2哗魂，5}、{3漓雅，4}录别、{3，5}邻吞、{4组题，5}、{5抱冷，6}以及{6崔列，7，8徘层，9}峻呕，共 7 個 α-極大團∪ばВ可是現(xiàn)在有了9個瘦癌，多出了兩個，這多出的兩個跷敬，可以通過驗證算法去掉讯私，以后再詳細介紹，這里不考慮，我只需要求出最后的9個極大團斤寇，就算完成任務(wù)桶癣。
下面是代碼：
頭文件：
Vertex_Value.h
#pragma once
#include <iostream>
using namespace std;
//這個相當于臨接表中的邊界點
class Vertex_Value
{
public:
Vertex_Value(void);
~Vertex_Value(void);
Vertex_Value(int x, float y);
public:
int vertex; //鄰接表中邊結(jié)點的編號
float val; //結(jié)點之間的概率
};
node.h
#pragma once
#include "Vertex_Value.h"
#include <vector>
using namespace std;
//相當于頭結(jié)點
class node
{
public:
int vertex; //頭節(jié)點的結(jié)點編號
vector<Vertex_Value> vec; //這里用vector動態(tài)數(shù)組來放邊結(jié)點，Vertex_Value表示邊結(jié)點娘锁，其中有結(jié)點編號牙寞，以及邊上的概率
};
UDG.h
#pragma once
#include "Vertex_Value.h"
#include <vector>
using namespace std;
//相當于頭結(jié)點
class node
{
#pragma once
#include "node.h"
class UDG
{
public:
int vernum, arcnum;
node *AdjVector;//是鄰接vector的形式 一個數(shù)組名字叫AdjVector,數(shù)組里面存放的是node形式的的數(shù)據(jù)
};
ReadFile.h
#pragma once
#include "UDG.h"
#define path "F:\\c++_code\\test2.txt"
//讀取文件
class ReadFile
{
public:
ReadFile(void);
~ReadFile(void);
void CreateUdg(UDG &g); //讀取文件后，構(gòu)建出不確定圖出來
};
BasicFunctions.h
#pragma once
#include <vector>
#include "UDG.h"
#include "Vertex_Value.h"
using namespace std;
#define $ 0.1 //概率閾值莫秆，極大團的團概率要大于這個值
class BasicFunctions
{
public:
BasicFunctions(void);
~BasicFunctions(void);
vector<UDG> Bron_Kerbosch(const UDG g);//把不確定圖作為確定圖來看待间雀，得到所有的極大團子圖
void MULE(const UDG g);//在不確定圖g中，找到所有團概率大于閾值的極大團
void EnumUncertainMC(vector<int> C, float q, vector<Vertex_Value> I, vector<Vertex_Value>& X, UDG g);//在MULE算法中枚舉圖中的極大團
vector<Vertex_Value> GenerateI(vector<int> C, float q, vector<Vertex_Value> I, UDG g);//在MULE算法中镊屎，用來更新I集合
vector<Vertex_Value> GenerateX(vector<int> C, float q, vector<Vertex_Value> X, UDG g);//在MULE算法中惹挟，用來更新X集合
void fuzhufunction(vector<int> C, float q, vector<Vertex_Value> I, vector<Vertex_Value>& X, int i, UDG g);//在MULE算法中的輔助函數(shù)
bool IfConnect(int u, int v, UDG g); //判斷在圖g中，結(jié)點u和結(jié)點v是否連接
void Enum_Deterministic(vector <int> all, vector <int> some, vector <int> none, UDG g);//用在Bron_Kerbosch算法中缝驳，枚舉圖中的極大團
vector<int> GenerateSome(vector <int> all, vector <int> some, UDG g);//用在Enum_Deterministic中连锯，更新其中的some集合
vector<int> GenerateNone(vector <int> all, vector <int> none, UDG g);//用在Enum_Deterministic中，更新其中的none集合
int MaxC(vector<int> C);//找當前團C中的最大頂點編號
vector<int> AdjVertex(int m, UDG g);//找到圖g中用狱，m結(jié)點的所有鄰接點
vector<int> mixede(vector<int> A, vector<int> B);//求兩個vector的交集
bool isbelongto(int m, vector<int> S1);//檢測m頂點是否屬于S1运怖；
float FindValue(int u, int v, UDG g);//給定頂點對，找權(quán)值
float clq(vector<int> C, float q, Vertex_Value D, int m, UDG g);//求當前團加入一個頂點后的團概率
vector<int> AdjVertex_MULE(int m, UDG g);//在MULE中使用齿拂，找到m的所有鄰居結(jié)點
float FindValue_MULE(int u, int v, UDG g);//在MULE中使用驳规，找到結(jié)點u和結(jié)點v之間的權(quán)值
};
下面是cpp文件：
Vertex_Value.cpp
#include "Vertex_Value.h"
Vertex_Value::Vertex_Value(void)
{
}
Vertex_Value::~Vertex_Value(void)
{
}
Vertex_Value::Vertex_Value(int x, float y)
{
vertex = x;
val = y;
}
ReadFile.cpp
#include "ReadFile.h"
#include <fstream>
#include <iostream>
using namespace std;
ReadFile::ReadFile(void)
{
}
ReadFile::~ReadFile(void)
{
}
void ReadFile::CreateUdg(UDG &g)
{
ifstream infile(path); //讀取path里面的文本
cout << "開始讀入文件！" << endl;
infile >> g.vernum >> g.arcnum; //infile在這里就類似cin操作署海，cin是讀取鍵盤輸入吗购，而infile是讀取文件輸入 >> 操作返回的是左操作數(shù)，也就是給g.vernum和g.arcnum賦值了
cout << "頂點個數(shù)和邊數(shù)為：" << endl;
cout << g.vernum << ' ' << g.arcnum << endl;
g.AdjVector = new node[g.vernum + 1];//0號不存結(jié)點砸狞，能儲存g.vernum個結(jié)點的數(shù)組AdjVector捻勉，g.AdjVector[0]中不存放數(shù)據(jù)
cout << "開始讀入邊，建立鄰接vector刀森！" << endl;
int i;
for (i = 0; i < g.arcnum; i++)
{
int head, tail;
float val;
infile >> head >> tail >> val; //文本里讀取文件到空格結(jié)束踱启，循環(huán)結(jié)束以后進入到下一行
g.AdjVector[head].vertex = head; //這樣可以完成順序存放，這樣g.AdjVector[1]中研底，存放的是頭節(jié)點為1的結(jié)點埠偿，其他結(jié)點也都是對應(yīng)的
Vertex_Value temp;
temp.vertex = tail;
temp.val = val;
g.AdjVector[head].vec.push_back(temp);
}
}
BasicFunctions.cpp
#include<algorithm>
#include <iterator>
#include "UDG.h"
#include "BasicFunctions.h"
vector<UDG> Amc;//用來裝Bron_Kerbosch算法產(chǎn)生的極大團子圖
BasicFunctions::BasicFunctions(void)
{
}
BasicFunctions::~BasicFunctions(void)
{
}
//***********************************************************************
//判斷在圖g中結(jié)點u和結(jié)點v是否相連
bool BasicFunctions::IfConnect(int u, int v, UDG g)
{
int i;
unsigned int j;
for (i = 1; i <= g.vernum; i++)
{
if (g.AdjVector[i].vertex == u)
{
break;
}
}
for (j = 0; j < g.AdjVector[i].vec.size(); j++)
{
if (v == g.AdjVector[i].vec[j].vertex)
{
//cout << "結(jié)點" << u << "和結(jié)點" << v << "相連" << endl;
return true;
}
}
//cout << "結(jié)點" << u << "和結(jié)點" << v << "不相連" << endl;
return false;
}
//***********************************************************************
//檢測m頂點是否屬于S1；
bool BasicFunctions::isbelongto(int m, vector<int> S1)
{
for (unsigned int i = 0; i < S1.size(); i++)
{
if (m == S1[i])
{
return true;
}
}
return false;
}
//***********************************************************************
//求兩個vector的交集
vector<int> BasicFunctions::mixede(vector<int> A, vector<int> B)
{
vector<int> v;
sort(A.begin(), A.end());
sort(B.begin(), B.end());
set_intersection(A.begin(), A.end(), B.begin(), B.end(), back_inserter(v));//求交集 ,必須引入<algorithm>榜晦、<iterator>才能使用這些函數(shù)
return v;
}
//***********************************************************************
//找當前團C中的最大頂點編號
int BasicFunctions::MaxC(vector<int> C)
{
if (C.empty())
{
return 0;
}
int max = 1;
unsigned int i;
for (i = 0; i < C.size(); i++)
{
if (max < C[i])
{
max = C[i];
}
}
return max;
}
//***********************************************************************
//找到圖g中冠蒋，m結(jié)點的所有鄰接點
vector<int> BasicFunctions::AdjVertex(int m, UDG g)
{
vector<int> C;
unsigned int i;
for (i = 0; i < g.AdjVector[m].vec.size(); i++)
{
C.push_back(g.AdjVector[m].vec[i].vertex);
}
return C;
}
//***********************************************************************
//找到圖g中，m結(jié)點的所有鄰接點
vector<int> BasicFunctions::AdjVertex_MULE(int m, UDG g)
{
vector<int> C;
int i;
unsigned int j;
for (i = 1; i <= g.vernum; i++)
{
if (g.AdjVector[i].vertex == m) break;
}
for (j = 0; j < g.AdjVector[i].vec.size(); j++)
{
C.push_back(g.AdjVector[i].vec[j].vertex);
}
return C;
}
//***********************************************************************
float BasicFunctions::FindValue_MULE(int u, int v, UDG g)
{
unsigned int i;
int j;
for (j = 1; j <= g.vernum; j++)
{
if (g.AdjVector[j].vertex == u) break;
}
for (i = 0; i < g.AdjVector[j].vec.size(); i++)
{
if (g.AdjVector[j].vec[i].vertex == v)
{
return g.AdjVector[j].vec[i].val;
}
}
return 0;
}
//***********************************************************************
//找到圖g中乾胶，結(jié)點u和結(jié)點v之間的權(quán)值
float BasicFunctions::FindValue(int u, int v, UDG g)
{
unsigned int i;
for (i = 0; i < g.AdjVector[u].vec.size(); i++)
{
if (g.AdjVector[u].vec[i].vertex == v)
{
return g.AdjVector[u].vec[i].val;
}
}
return 0;
}
//***********************************************************************
//這個是求抖剿，如果將結(jié)點D加入加入極大團C后朽寞，團概率會變成什么值
float BasicFunctions::clq(vector<int> C, float q, Vertex_Value D, int m, UDG g)
{
float temp;
temp = FindValue_MULE(D.vertex, m, g);
return q * D.val * temp;
}
//***********************************************************************
//在MULE算法中，用來更新X集合
vector<Vertex_Value> BasicFunctions::GenerateX(vector<int> C, float q, vector<Vertex_Value> X, UDG g)
{
if (X.empty())
{
return X;
}
int m = MaxC(C);
vector<int> S2 = AdjVertex_MULE(m, g);
vector<Vertex_Value> _X;
vector<int> S1;
unsigned int i;
for (i = 0; i < X.size(); i++)
{
S1.push_back(X[i].vertex);
}
S1 = mixede(S1, S2);
unsigned int j;
for (i = 0, j = 0; i < X.size(); i++)
{
if (isbelongto(X[i].vertex, S1))
{
if (clq(C, q, X[i], m, g) >= $)
{
_X.push_back(X[i]);
_X[j].val = _X[j].val * FindValue_MULE(_X[j].vertex, m, g);
j++;
}
}
}
return _X;
}
//***********************************************************************
//在MULE算法中斩郎，用來更新I集合
vector<Vertex_Value> BasicFunctions::GenerateI(vector<int> C, float q, vector<Vertex_Value> I, UDG g)
{
int m = MaxC(C); //找到C中編號最大的點
vector<int> S2 = AdjVertex_MULE(m, g); //在圖g中找到m的鄰居接點
vector<Vertex_Value> _I;
vector<int> S1;
unsigned int i;
for (i = 0; i < I.size(); i++)
{
S1.push_back(I[i].vertex);
}
S1 = mixede(S1, S2);
unsigned int j = 0;
for (i = 0, j; i < I.size(); i++)
{
if (I[i].vertex > m && isbelongto(I[i].vertex, S1))
{
if (clq(C, q, I[i], m, g) >= $)
{
_I.push_back(I[i]);
_I[j].val = _I[j].val * FindValue_MULE(_I[j].vertex, m, g);
j++;
}
}
}
return _I;
}
//***********************************************************************
//EnumUncertainMC中的輔助函數(shù)
void BasicFunctions::fuzhufunction(vector<int> C, float q, vector<Vertex_Value> I, vector<Vertex_Value>& X, int i, UDG g)
{
C.push_back(I[i].vertex);
q = q * I[i].val;
vector<Vertex_Value> _I = GenerateI(C, q, I, g);
vector<Vertex_Value> _X = GenerateX(C, q, X, g);
EnumUncertainMC(C, q, _I, _X, g);
X.push_back(I[i]);
}
//***********************************************************************
//在MULE算法中脑融，找到滿足要求的極大團
void BasicFunctions::EnumUncertainMC(vector<int> C, float q, vector<Vertex_Value> I, vector<Vertex_Value>& X, UDG g)
{
unsigned int i;
if (I.empty() && X.empty())
{
cout << "通過MULE算法產(chǎn)生一個極大團！" << endl;
for (i = 0; i < C.size(); i++)
{
cout << C[i] << ' ';
}
cout << endl;
return;
}
vector<int> Ctemp(C);
for (i = 0; i < I.size(); i++)
{
fuzhufunction(Ctemp, q, I, X, i, g);
}
}
//***********************************************************************
//用在Enum_Deterministic中缩宜，更新其中的none集合
vector<int> BasicFunctions::GenerateNone(vector <int> all, vector <int> none, UDG g)
{
int m = MaxC(all); //找到C中編號最大的點
vector<int> S2 = AdjVertex(m, g); //在圖g中找到m的鄰居接點
vector<int> _none;
vector<int> S1;
unsigned int i;
for (i = 0; i < none.size(); i++)
{
S1.push_back(none[i]);
}
S1 = mixede(S1, S2); //保證some中放的結(jié)點肘迎，都是和all中所有結(jié)點連接的
for (i = 0; i < none.size(); i++)
{
if (isbelongto(none[i], S1))
{
_none.push_back(none[i]);
}
}
return _none;
}
//***********************************************************************
//用在Enum_Deterministic中，更新其中的some集合
vector<int> BasicFunctions::GenerateSome(vector <int> all, vector <int> some, UDG g)
{
int m = MaxC(all); //找到all中編號最大的點
vector<int> S2 = AdjVertex(m, g); //在圖g中找到m的鄰居接點
vector<int> _some;
vector<int> S1;
unsigned int i;
for (i = 0; i < some.size(); i++)
{
S1.push_back(some[i]);
}
S1 = mixede(S1, S2); //保證some中放的結(jié)點锻煌，都是和all中所有結(jié)點連接的
for (i = 0; i < some.size(); i++)
{
if (some[i] > m && isbelongto(some[i], S1))
{
_some.push_back(some[i]);
}
}
return _some;
}
//***********************************************************************
//用在Bron_Kerbosch算法中膜宋，枚舉圖中的極大團
void BasicFunctions::Enum_Deterministic(vector <int> all, vector <int> some, vector <int> none, UDG g)
{
unsigned int i;
if (some.empty() && none.empty()) //兩者都為空，則找到極大團
{
UDG g_t;
g_t.vernum = all.size();
g_t.arcnum = (all.size()*(all.size()-1));
g_t.AdjVector = new node[all.size() + 1];
cout << "通過Bron_Kerbosch算法產(chǎn)生一個極大團子圖炼幔！" << endl;
for (i = 0; i < all.size(); i++)
{
cout << all[i] << ' ';
g_t.AdjVector[i + 1] = g.AdjVector[all[i]];
}
cout << endl;
Amc.push_back(g_t);
return;
}
vector<int> allTemp(all); //將all中的所有值，都賦給allTemp史简，allTemp用來遞歸到下一層（去放置極大團）
for (i = 0; i < some.size(); i++)
{
allTemp.push_back(some[i]);//更新下一層中的allTemp
vector<int> _some = GenerateSome(allTemp, some, g);//產(chǎn)生新的some集合乃秀。要保證新的some集合，要和allTemp集合中的所有結(jié)點都連接
vector<int> _none = GenerateNone(allTemp, none, g);//產(chǎn)生新的none集合圆兵。要保證新的none集合跺讯，要和allTemp集合中的所有結(jié)點都連接
Enum_Deterministic(allTemp, _some, _none, g); //帶著新的all,some,none集合進入到下一層中
none.push_back(some[i]);//將some[i]放入none中，表示在這一層里面殉农，由some[i]開始的極大團刀脏，已經(jīng)探索過了
allTemp.pop_back(); //將some[i]從allTemp中拿出，開始下一輪的for循環(huán)超凳，在下一輪的for循環(huán)中愈污，放入新的some[i]
}
}
//***********************************************************************
//總算法的第一步，從原圖中得到所有的極大團子圖
vector<UDG> BasicFunctions::Bron_Kerbosch(const UDG g)
{
vector <int> some(g.vernum);//聲明一個初始大小為g.vernum的Vertex_Value類型的向量_I轮傍，_I中存放的結(jié)點暂雹，就是預(yù)備要放入C中的
vector<int> all; //聲明一個int型向量all，就是極大團
vector<int> none; //聲明一個Vertex_Value型向量X 创夜，X存放已經(jīng)探索過的某結(jié)點杭跪。
int i = 1;
for (i; i <= g.vernum; i++)
{
some[i - 1] = i; //將所有的結(jié)點編號存放在some中
}
Enum_Deterministic(all, some, none, g);
return Amc;
}
//***********************************************************************
//總算法的第二步，從每個極大團子圖中驰吓，找到滿足概率閾值的極大團
void BasicFunctions::MULE(const UDG g)
{
vector <Vertex_Value> _I(g.vernum);//聲明一個初始大小為g.vernum的Vertex_Value類型的向量_I涧尿，_I中存放的結(jié)點，就是預(yù)備要放入C中的
vector<int> C; //聲明一個int型向量C
vector<Vertex_Value> X; //聲明一個Vertex_Value型向量X 檬贰，X存放已經(jīng)探索過的某結(jié)點姑廉。
int i = 1;
for (i; i <= g.vernum; i++) //先初始化_I，其中存放（u,r）偎蘸，其中u就是Vertex_Value中的vertex（表示結(jié)點的編號）庄蹋，r就是Vertex_Value中的val（表示將該節(jié)點加入到極大團C后瞬内，所要乘上的概率）
{
_I[i - 1].vertex = g.AdjVector[i].vertex;
_I[i - 1].val = 1; //最開始都賦值為1
}
float j = 1;
EnumUncertainMC(C, j, _I, X, g);
}
下面是主函數(shù)：
#include <tchar.h>
#include "ReadFile.h"
#include "BasicFunctions.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
UDG g;
ReadFile A;
vector<UDG> Amc;
A.CreateUdg(g);
BasicFunctions BF;
Amc = BF.Bron_Kerbosch(g);
unsigned int i;
for (i = 0; i < Amc.size(); i++)
{
BF.MULE(Amc[i]);
}
system("pause"); //暫停黑窗口
return 0;
}
test2.txt如下:
9表示結(jié)點數(shù)，28表示邊數(shù)（這里的1 2和2 1算不同的邊）
第一位數(shù)字是頭結(jié)點限书，第二位數(shù)字是邊結(jié)點虫蝶，第三個數(shù)字是邊上的概率
9 28
1 2 0.6
1 3 0.5
2 1 0.6
2 3 0.4
2 5 0.7
3 1 0.5
3 2 0.4
3 4 0.5
3 5 0.1
4 3 0.5
4 5 0.2
5 2 0.7
5 3 0.1
5 4 0.2
5 6 0.4
6 5 0.4
6 7 0.7
6 8 0.9
6 9 0.8
7 6 0.7
7 8 0.7
7 9 0.6
8 6 0.9
8 7 0.7
8 9 0.6
9 6 0.8
9 7 0.6
9 8 0.6
實驗結(jié)果：
實驗結(jié)果
