RankVote_重要节点组挖掘

1

nth_element(a.begin(), a.begin() + num, a.end(), cmp);

1
2
3
4
5

1.初始化每个结点的分数为0，投票能力为1
2.遍历图，每个结点的分数为直接相连结点的投票能力之和
3.找出分数最高的结点 P，将 P 加入初始结点选集中
4.修改 P 的分数和投票能力为0，削弱 P 直接相连的结点，幅度为度的期望的倒数
5.重复 2-4 步，直至选出 num 个结点

1
2
3
4
5

1.初始化每个结点的分数为该节点的度，投票能力为1
2.找出分数最高的结点 P，将 P 加入初始结点选集中
3.修改 P 的分数和投票能力为0
4.削弱 P 直接相连的结点，削弱与该结点直接相连的点的分数，幅度为度的期望的倒数
5.重复 2-4 步，直至选出 num 个结点

1
2
3
4
5

1.将初始传播结点入队列
2.取队首结点弹出并设为 R 类型结点
3.遍历与它直接相连的 I 类型结点，每一个以 beta 的概率被传染为 S
4.第三步中被传染的结点加入队列中
5.重复 2-4 步直至队列为空，统计所有被传染过的结点的数量，即规模

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

$ tree -L 2
.
|-- Makefile
|-- data
|   |-- USAir.txt
|   |-- network.txt
|   |-- result.out
|   |-- router.txt
|   `-- sex.txt
|-- output
|   `-- main.exe
`-- src
    |-- main.cpp
    `-- main.o

3 directories, 9 files

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

#include <algorithm>
#include <ctime>
#include <iostream>
#include <numeric>
#include <queue>
#include <random>
#include <vector>
typedef long long ll;
using namespace std;
vector<int> Du, Vote;
vector<vector<int> > G;

void SelectByDu(int num);
void SelectByVote(int num);
bool cmp(int x, int y);
double Rand();
int TestSIR(vector<int> InitNode);

double f;
int n, m, u, v;
int num;              /* 选出的初始传播结点数目 */
double pjlunci = 500; /* 求平均值的轮数 */
vector<int> cntDu, cntVote;
double meanDu, meanVote, varianceDu, varianceVote;
double averageK, averageK2;
double SIRbeta, SIRalpha;

struct votenode {
  double score = 0, value = 1;
};

int main(int argc, char *argv[]) {
  srand(time(NULL));
  num = atoi(argv[2]);
  // SIRalpha = atof(argv[3]);
  SIRbeta = atof(argv[3]);
  freopen(argv[1], "r", stdin);
  freopen("data\\result.out", "w", stdout);
  cin >> n >> m;
  cout << "[+] vertices : " << n << " edges : " << m << endl;
  cout << "[+] the num of selected is " << num << endl;

  G.resize(n);
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    G[u].push_back(v), G[v].push_back(u);
  }
  averageK = 2.0 * m / n;
  f = 1.0 / averageK;

  SelectByDu(num);
  SelectByVote(num);

  for (auto &i : G) averageK2 += pow(i.size(), 2) / (double)n;

  // SIRbeta = SIRalpha * (averageK / averageK2);

  cout << "averageK = " << averageK << " averageK2 =" << averageK2 << "\n"
       << endl;
  cout << "SIRbeta = " << SIRbeta << "\n" << endl;

  for (int i = 0; i < pjlunci; i++) {
    cntDu.push_back(TestSIR(Du)), cntVote.push_back(TestSIR(Vote));
  }
  meanDu = accumulate(cntDu.begin(), cntDu.end(), 0.0) / pjlunci;
  meanVote = accumulate(cntVote.begin(), cntVote.end(), 0.0) / pjlunci;

  for (int i = 0; i < pjlunci; i++) {
    varianceDu += pow(cntDu[i] - meanDu, 2) / n;
    varianceVote += pow(cntVote[i] - meanVote, 2) / n;
  }

  cout << "[+] the mean of Du: " << meanDu
       << "    the variance of Du: " << varianceDu << endl;
  cout << "[+] the mean of Vote: " << meanVote
       << "    the variance of Vote: " << varianceVote << endl;
  cout << "rate : " << (meanVote - meanDu) / meanDu * 100 << " %" << endl;
  return 0;
}

bool cmp(int x, int y) { return G[x].size() > G[y].size(); }
double Rand() { return (double)rand() / RAND_MAX; }

// 以度为顺序选出前 num 大的节点
void SelectByDu(int num) {
  clock_t start, finish;
  start = clock();
  vector<int> a(n);
  for (int i = 0; i < n; i++) a[i] = i;
  nth_element(a.begin(), a.begin() + num, a.end(), cmp);
  cout << "[+] Select by degree of vertex" << endl;
  for (int i = 0; i < num; i++) Du.push_back(a[i]);
  sort(Du.begin(), Du.end(), cmp);
  // for (int i = 0; i < num; i++) {
  //   cout << Du[i] << " ";
  // }

  finish = clock();
  cout << endl
       << "[-] the time cost is:" << double(finish - start) / CLOCKS_PER_SEC
       << endl
       << endl;
}

void SelectByVote(int num) {
  clock_t start, finish;
  start = clock();
  vector<votenode> S(n);
  vector<int> vis(n);
  for (int i = 0; i < n; i++) {
    S[i].score = G[i].size(), S[i].value = (double)1;
  }
  while (num--) {
    double maxScore = -1;
    int p = -1;
    for (int i = 0; i < n; i++) {
      if (S[i].score > maxScore) {
        maxScore = S[i].score;
        p = i;
      }
    }

    if (maxScore == 0) {
      for (int i = 0; i < n; i++) {
        if (!vis[i]) {
          p = i;
          break;
        }
      }
    }
    vis[p] = 1;
    for (int i = 0; i < (int)G[p].size(); i++) {
      u = G[p][i];
      S[u].score -= S[p].value;
      double deltaval = S[u].value - max(S[u].value - f, (double)0);
      S[u].value = max(S[u].value - f, (double)0);
      for (int j = 0; j < (int)G[u].size(); j++) {
        v = G[u][j];
        S[v].score = max(S[v].score - deltaval, (double)0);
      }
    }
    S[p].score = S[p].value = 0;
    Vote.push_back(p);
  }

  cout << "[+] Select by vote of vertex" << endl;
  // for (int i = 0; i < (int)Vote.size(); i++) {
  //   cout << Vote[i] << " ";
  // }
  finish = clock();
  cout << endl
       << "[-] the time cost is:" << double(finish - start) / CLOCKS_PER_SEC
       << endl
       << endl;
}

int TestSIR(vector<int> InitNode) {
  vector<int> T(n, 0);
  queue<int> infected;
  for (auto &i : InitNode) {
    T[i] = 1;
    infected.push(i);
  }
  int infectedNum = InitNode.size(), infectCount = 0;
  while (!infected.empty()) {
    u = infected.front();
    infected.pop();
    T[u] = -1;
    for (int j = 0; j < (int)G[u].size(); j++) {
      v = G[u][j];
      if (T[v] == 0 && Rand() <= SIRbeta) {
        T[v] = 1;
        infected.push(v);
        infectedNum++;
      }
    }
    infectCount++;
  }
  return infectCount;
}