TFG

This is a repository created to keep track of changes in the code for my degree's final project.

girvan_newman.py

Module of the Girvan Newman Algorithm. It is used in the comparativeAnalysis.ipynb notebook. It implements helper methods like "edge_betweenness(graph)", the algorithm itself in "girvan_newman2004(graph)" and drawing methods like "draw_communities(graph, community)".

The method proposed is the one described in "Community structure in social and biological networks" by Girvan and Newman in 2002 (available at https://arxiv.org/abs/cond-mat/0112110), as well as the one proposed in "Finding and evaluating community structure in networks" by Newman and Girvan in 2004 (available at https://arxiv.org/abs/cond-mat/0308217).

louvain.py

Module of the Louvain Algorithm. It is used in the comparativeAnalysis.ipynb notebook. It implements helper methods like "last_community(graph,communities)", the algorithm itself in "louvain(graph)" and drawing methods like "draw_communities(graph, community)".

The method proposed is the one described in "Fast unfolding of communities in large networks" by Blondel, also known as the Louvain method (article available at: https://arxiv.org/abs/0803.0476).

comparativeAnalysis.ipynb

A comparative analysis of the girvan-newman and louvain methods. Here we measure the modularity of the partition generated by the algorithms and the running time of each method using the datasets game-of-thrones-books/book1.csv, facebook/socfb-Haverford.txt and marvel-social-newtork/heroes.csv

marvel-vs-dc

A short notebook using the marvel-vs-dc.csv dataset, which contains the names of Marvel and DC movies and their respective release date, rate and earnings. The notebook tries to represent these movies as an unweighted undirected graph, in order to see the communities that describe such graph. The method used to achieve this goal is the Girvan-Newman algorithm, implemented in the Networkx python package.

dev_girvanNewman (Girvan-Newman Algorithm)

A notebook that implements the Girvan-Newman algorithm for the graph contained in the marvel-social-network.csv dataset. Networkx.Graph representation is used, but functionality of the Girvan-Newman algorithm is manually implemented.

marvel-social-network-Louvain (Louvain Algorithm)

A notebook that implements the Louvain Algorithm for the graph contained in the marvel-social-network.csv dataset. Networkx.Graph representation is used, but functionality of the Louvain algorithm is manually implemented.