spbu-coding-2023 / graphs-graph-10

graphs-graph-10 created by GitHub Classroom
MIT License
20 stars 0 forks source link

added LeaderRankAlgo for finding key vertices #57

Closed Dabzelos closed 4 months ago

Dabzelos commented 4 months ago

added: parameterizable LeaderRank algorithm also added visualization for this algorithm To see the results click "Find Key vertices with leader Rank" button image You'll see the dialogue window with parameters to input: image you may input amount of vertices XOR the gap of ranks to see after that TopRankedVertices will be coloured with red image

the idea of algorithn itself: LeaderRank(graph G, damping_factor d, convergence_threshold epsilon)

  1. Initialize the vertex ratings: each vertex v_i has a rating R(v_i) = 1 / |V|, where |V| is the total number of vertices in graph G.
  2. Let's construct the adjacency matrix A of graph G.
  3. Let's construct a matrix of transition probabilities P: P = A / deg, where deg is the number of outgoing edges for each vertex.
  4. Repeat until convergence: 4.1. Calculate the new vertex ratings: R_new = (1-d) / | V| + d P R, where d is the attenuation coefficient. 4.2. Calculate the change in ratings: diff = ||R_new - R|| 4.3. If diff < epsilon, interrupt the iterations. 4.4. Assign R = R_new and continue iterating.
  5. We display the ratings of the vertices in descending order.
xamelllion commented 4 months ago

photo_2024-05-25_23-49-07