SheepHunter/community_algorithm.py at main · FIND-Lab/SheepHunter · GitHub

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
import numpy as np
from tqdm import tqdm


def algorithm_iter(total_length, non_empty_process_index, similarity_matrix, threshold_size, method="louvain_iter"):


  def community_find(similarity_matrix, method, g=None):
    if method == "kmedoids_iter":
      import sklearn_extra.cluster
      # predict_community = sklearn.cluster.KMeans(n_clusters=2).fit_predict(1 / (1e-4 + similarity_matrix))
      predict_community = sklearn_extra.cluster.KMedoids(n_clusters=2, metric="precomputed").fit_predict(1 / (1e-4 + similarity_matrix))

    elif method == "dbscan_iter":
      import sklearn.cluster
      results = sklearn.cluster.DBSCAN(metric="precomputed").fit_predict(1 / (1e-4 + similarity_matrix))
      for i in range(len(results)):
        if results[i] == -1: results[i] = np.max(results) + 1
      predict_community = results

    elif method == "louvain_iter":
      import igraph

      num_nodes = similarity_matrix.shape[0]

      results : igraph.VertexClustering = g.community_multilevel(weights="weight")

      predict_community = np.ones(num_nodes) - 1
      for i in range(len(results)):
        predict_community[results[i]] = i
      assert(np.sum(predict_community < 0) == 0)

    return predict_community

  predict_label = np.zeros(total_length) - 1
  predict_community_size = np.zeros(total_length)
  predict_community = np.zeros(total_length) - 1
  # set empty process
  empty_process_index = list(set([i for i in range(len(predict_community_size))]) - set(non_empty_process_index))
  predict_community_size[empty_process_index] = 100
  predict_label[empty_process_index] = 1

  community_sizes = {}
  non_empty_process_community = np.array([-1 for _ in range(len(similarity_matrix))])
  community_index = 0
  q = [[similarity_matrix, np.array([i for i in range(len(similarity_matrix))])]]
  non_empty_process_label = np.ones(similarity_matrix.shape[0])
  non_empty_process_size = np.zeros(similarity_matrix.shape[0])
  round_count = 0

  progress = tqdm(range(len(similarity_matrix)), desc=f"Processing in round {round_count}")

  if "louvain" in method:
    import igraph

    num_nodes = similarity_matrix.shape[0]
    edges = []
    weights = []

    for i in range(num_nodes):
      dst_index = np.where(similarity_matrix[i, :] > 0)[0]
      dst_index = dst_index[dst_index > i]
      weights.extend(similarity_matrix[i, dst_index].tolist())
      edge_tuple = np.ones([len(dst_index), 2]).astype(int)
      edge_tuple[:, 0] = i
      edge_tuple[:, 1] = dst_index
      edges.extend(edge_tuple.tolist())

    whole_graph = igraph.Graph(n=num_nodes, edges=edges, directed=False, edge_attrs={"weight": weights})
    print("Finish building graph")

  while len(q) != 0:
    round_count += 1
    similarity_matrix_sub, indexes = q.pop(0)
    if method == "louvain_iter":
      community_number = community_find(similarity_matrix_sub, method, whole_graph.subgraph(indexes))
    else:
      community_number = community_find(similarity_matrix_sub, method)
    community_size_dict = dict([(i, np.sum(community_number == i)) for i in set(community_number)])
    if len(community_size_dict) == 1 and community_size_dict[0] > threshold_size:
      community_sizes[community_index] = community_size_dict[0]
      non_empty_process_size[indexes] = community_size_dict[0]
      non_empty_process_label[indexes] = 1
      non_empty_process_community[indexes] = community_index
      community_index += 1
      progress.update(community_size_dict[0])
      progress.set_description(f"Processing in round {round_count}")
      continue
    for c_num, c_size in community_size_dict.items():
      if c_size <= threshold_size:
        community_sizes[community_index] = c_size
        non_empty_process_label[indexes[community_number == c_num]] = 0
        non_empty_process_size[indexes[community_number == c_num]] = c_size
        non_empty_process_community[indexes[community_number == c_num]] = community_index
        community_index += 1
        progress.update(c_size)
        progress.set_description(f"Processing in round {round_count}")
      else:
        q.append([similarity_matrix[indexes[community_number == c_num], :][:, indexes[community_number == c_num]], indexes[community_number == c_num]])
  progress.close()

  predict_community[non_empty_process_index] = non_empty_process_community
  assert(np.sum(predict_community == -1) == len(empty_process_index))
  predict_community[empty_process_index] = -1
  predict_label[non_empty_process_index] = non_empty_process_label
  predict_community_size[non_empty_process_index] = non_empty_process_size
  assert(np.sum(predict_label == -1) == 0)
  assert(np.sum(predict_community == -1) == len(empty_process_index))
  assert(np.sum(predict_community_size == 0) == 0)

  return predict_label, predict_community, predict_community_size

def cluster_density(total_length, non_empty_process_index, similarity_matrix, threshold_size, method):

  distance_matrix = 1 / (similarity_matrix + 1e-4)
  del similarity_matrix

  predict_label = np.zeros(total_length) - 1
  predict_community_size = np.zeros(total_length)
  predict_community = np.zeros(total_length) - 1

  import sklearn.cluster
  if method == "dbscan":
    non_empty_process_community = sklearn.cluster.DBSCAN(metric="precomputed").fit_predict(distance_matrix)

  for i in range(len(non_empty_process_community)):
    if non_empty_process_community[i] == -1: non_empty_process_community[i] = np.max(non_empty_process_community) + 1


  empty_process_index = list(set([i for i in range(len(predict_community_size))]) - set(non_empty_process_index))

  predict_label[empty_process_index] = 1
  predict_community[empty_process_index] = -1
  predict_community_size[empty_process_index] = 0xFFFFFFFF

  predict_community[non_empty_process_index] = non_empty_process_community
  for i in range(len(non_empty_process_index)):
    index = non_empty_process_index[i]
    community_id = non_empty_process_community[i]
    predict_community_size[index] = np.sum(predict_community == community_id)
    predict_label[index] = (np.sum(predict_community == community_id) >= threshold_size) + 0

  return predict_label, predict_community, predict_community_size