<reponame>NefeliTav/Recommender-Systems
import networkx as nx
import csv
import pprint as pp
import matplotlib.pyplot as plt


def good_local_community(graph, seed_node_id, alpha=0.9):

    # Creation of the teleporting probability distribution for the selected node...
    probability = {}
    for node_id in graph:
        probability[node_id] = 0.
    probability[seed_node_id] = 1.
    # Computation of the PageRank vector.
    pr = nx.pagerank(graph, alpha=alpha,
                     personalization=probability, max_iter=600)

    # Put all nodes in a list and sort the list in descending order of the normalized score
    sorted_list = [(node_id, score / graph.degree[node_id])
                   for node_id, score in pr.items()]
    sorted_list.sort(key=lambda x: (-x[1], x[0]))

    # LET'S SWEEP!
    index_maximum_conductance = -1
    min_conductance_value = float("+inf")
    candidate_community_nodes = set()
    rest_nodes = set(
        graph.nodes())
    for sweep_index in range(0, len(sorted_list) - 1):

        # Creation of the set of nodes representing the candidate community and
        # its complement to the entire set of nodes in the graph.
        current_node_id = sorted_list[sweep_index][0]
        candidate_community_nodes.add(current_node_id)
        rest_nodes.remove(
            current_node_id)

        # Evaluation of the quality of the candidate community according to its conductance value.
        conductance_value = nx.algorithms.cuts.conductance(graph,
                                                           candidate_community_nodes,
                                                           rest_nodes)
        # Discard local communities with conductance 0 or 1.
        if conductance_value == 0. or conductance_value == 1.:
            continue
        # Update the values of variables representing the best solution generated so far.
        if conductance_value < min_conductance_value:
            min_conductance_value = conductance_value
            index_maximum_conductance = sweep_index
    # Creation of the set of nodes representing the best local community generated by the sweeping procedure.
    minimum_conductance_nodes = set([node_id for node_id, normalized_score in
                                     sorted_list[
                                         :index_maximum_conductance + 1]])
    return minimum_conductance_nodes, min_conductance_value


input_graph = "../dataset/pkmn_graph_data.tsv"
# Graph creation by reading the list of unweighted edges from file
file_handler = open(input_graph, 'r', encoding="utf-8")
csv_reader = csv.reader(file_handler, delimiter='\t',
                        quotechar='"', quoting=csv.QUOTE_NONE)
u_v = []
graph = nx.Graph()
for record in csv_reader:
    u = record[0]
    v = record[1]
    graph.add_edge(u, v)

file_handler.close()

alpha = [0.95, 0.9, 0.85, 0.8, 0.75, 0.7, 0.65, 0.6, 0.55,
         0.5, 0.45, 0.4, 0.35, 0.3, 0.25, 0.2, 0.15, 0.1, 0.05]

pokemon_in_communities = {}
for node_id in graph:
    pokemon_in_communities[node_id] = 0
for node_id in graph:
    max_conductance = float("-inf")
    for damping_factor in alpha:
        local_community, conductance = good_local_community(
            graph, node_id, alpha=damping_factor)
        if (conductance == 0 or conductance == 1 or len(local_community) > 140):
            continue
        if (conductance > max_conductance):
            max_conductance = conductance
            max_community = local_community
            best_a = damping_factor

import networkx as nx
import csv
import pprint as pp
import matplotlib.pyplot as plt


def good_local_community(graph, seed_node_id, alpha=0.9):

    # Creation of the teleporting probability distribution for the selected node...
    probability = {}
    for node_id in graph:
        probability[node_id] = 0.
    probability[seed_node_id] = 1.
    # Computation of the PageRank vector.
    pr = nx.pagerank(graph, alpha=alpha,
                     personalization=probability, max_iter=600)

    # Put all nodes in a list and sort the list in descending order of the normalized score
    sorted_list = [(node_id, score / graph.degree[node_id])
                   for node_id, score in pr.items()]
    sorted_list.sort(key=lambda x: (-x[1], x[0]))

    # LET'S SWEEP!
    index_maximum_conductance = -1
    min_conductance_value = float("+inf")
    candidate_community_nodes = set()
    rest_nodes = set(
        graph.nodes())
    for sweep_index in range(0, len(sorted_list) - 1):

        # Creation of the set of nodes representing the candidate community and
        # its complement to the entire set of nodes in the graph.
        current_node_id = sorted_list[sweep_index][0]
        candidate_community_nodes.add(current_node_id)
        rest_nodes.remove(
            current_node_id)

        # Evaluation of the quality of the candidate community according to its conductance value.
        conductance_value = nx.algorithms.cuts.conductance(graph,
                                                           candidate_community_nodes,
                                                           rest_nodes)
        # Discard local communities with conductance 0 or 1.
        if conductance_value == 0. or conductance_value == 1.:
            continue
        # Update the values of variables representing the best solution generated so far.
        if conductance_value < min_conductance_value:
            min_conductance_value = conductance_value
            index_maximum_conductance = sweep_index
    # Creation of the set of nodes representing the best local community generated by the sweeping procedure.
    minimum_conductance_nodes = set([node_id for node_id, normalized_score in
                                     sorted_list[
                                         :index_maximum_conductance + 1]])
    return minimum_conductance_nodes, min_conductance_value


input_graph = "../dataset/pkmn_graph_data.tsv"
# Graph creation by reading the list of unweighted edges from file
file_handler = open(input_graph, 'r', encoding="utf-8")
csv_reader = csv.reader(file_handler, delimiter='\t',
                        quotechar='"', quoting=csv.QUOTE_NONE)
u_v = []
graph = nx.Graph()
for record in csv_reader:
    u = record[0]
    v = record[1]
    graph.add_edge(u, v)

file_handler.close()

alpha = [0.95, 0.9, 0.85, 0.8, 0.75, 0.7, 0.65, 0.6, 0.55,
         0.5, 0.45, 0.4, 0.35, 0.3, 0.25, 0.2, 0.15, 0.1, 0.05]

pokemon_in_communities = {}
for node_id in graph:
    pokemon_in_communities[node_id] = 0
for node_id in graph:
    max_conductance = float("-inf")
    for damping_factor in alpha:
        local_community, conductance = good_local_community(
            graph, node_id, alpha=damping_factor)
        if (conductance == 0 or conductance == 1 or len(local_community) > 140):
            continue
        if (conductance > max_conductance):
            max_conductance = conductance
            max_community = local_community
            best_a = damping_factor
# Creation of the teleporting probability distribution for the selected node... # Computation of the PageRank vector. # Put all nodes in a list and sort the list in descending order of the normalized score # LET'S SWEEP! # Creation of the set of nodes representing the candidate community and # its complement to the entire set of nodes in the graph. # Evaluation of the quality of the candidate community according to its conductance value. # Discard local communities with conductance 0 or 1. # Update the values of variables representing the best solution generated so far. # Creation of the set of nodes representing the best local community generated by the sweeping procedure. # Graph creation by reading the list of unweighted edges from file