from networkit import *

%matplotlib inline

cd ~/Documents/workspace/NetworKit

G = readGraph("input/PGPgiantcompo.graph", Format.METIS)

# Code for 7-1)
# exact computation
bc = centrality.Betweenness(G, True)
%time bc.run()
bc.ranking()[:15]

# Code for 7-2)
# approximate computation
bca = centrality.ApproxBetweenness(G, 0.05)
%time bca.run()
bca.ranking()[:15]

"""
Explanation: Solutions to
Tutorial "Algorithmic Methods for Network Analysis with NetworKit" (Part 4)
Determining Important Nodes (cont'd)
Betweenness Centrality
If you interpret the Facebook graph as web link graph in the previous Q&A session, the obvious ranking choice is the PageRank. Note that today it is only one of many aspects modern web search engines consider to rank web pages. However, we were looking for the eigenvector centrality as MIT8 is a social network (both and possibly others can be applicable, though).
In applications where the flow of goods, vehicles, information, etc. via shortest paths in a network plays a major role, betweenness centrality is an interesting centrality index. It is also widely used for social networks. Its drawback is its rather high running time, which makes its use problematic for really large networks. But in many applications we do not need to consider the exact betweenness values nor an exact ranking. An approximation is often good enough.
Q&A Session #7


In the PGP network, compute the 15 nodes with the highest (exact) betweenness values and order them accordingly in a ranking.
Answer:


Perform the same as in 1) with one difference: Instead of using the algorithm for computing exact betweenness values, use the RK approximation algorithm. Use also values different from the default ones for the parameters $\delta$ and $\epsilon$. What effects do you see in comparison to the ranking based on exact values? What about running time (you can use %time preceding a call to get its CPU time)? And how do the parameter settings affect these effects?
Answer:
End of explanation
"""


community.detectCommunities(G)

"""
Explanation: Community Detection
This section demonstrates the community detection capabilities of NetworKit. Community detection is concerned with identifying groups of nodes which are significantly more densely connected to each other than to the rest of the network.
Code for community detection is contained in the community module. The module provides a top-level function to quickly perform community detection with a suitable algorithm and print some stats about the result.
End of explanation
"""


community.detectCommunities(G, algo=community.PLP(G))

"""
Explanation: The default setting uses the parallel Louvain method (PLM) as underlying algorithm. The function prints some statistics and returns the partition object representing the communities in the network as an assignment of node to community label. PLM yields a high-quality solution at reasonably fast running times. Let us now apply other algorithms. To this end, one specifies the algorithm directly in the call.
End of explanation
"""


communities = _
viztasks.drawCommunityGraph(G, communities)

"""
Explanation: The visualization module, which is based on external code for graph drawing, provides a function which visualizes the community graph for a community detection solution: Communities are contracted into single nodes whose size corresponds to the community size. For problems with hundreds or thousands of communities, this may take a while.
End of explanation
"""


# Code for 8-1) and 8-2)
community.detectCommunities(G, algo=community.PLM(G,True))
communities = _
viztasks.drawCommunityGraph(G, communities)

"""
Explanation: Q&A Session 8


Run PLMR as well. What are the main differences between the three algorithms PLM, PLMR, and PLP in terms of the solutions they compute and the time they need for this computation?
Answer:


Visualize the three results. Can you see aspects of your answer to 1) in the figure as well? Do the figures lead to other insights?
Answer:
End of explanation
"""


