Using modified Floyd-Warshall and modified BFS
Explore the repository»
View Problem Statement
tags : betweenness centrality, ventrality, graphs, graph theory
This program performs the betweenness centrality calculation in networks represented as undirected graphs. Betweenness centrality is a measure of the importance of a particular node in a network. The entire program is written in three files - client.c
, header.c
, and implement.c
. Comments have been added frequently to help in understanding the logic behind implementation. The program expects the user to save all the graphs to be processed in the 'graphs' directory in edge list format and to input the filename during execution. The user is provided with the option of either displaying the betweenness centrality on screen or to save it in a file in 'results' directory (by calling appropriate function). The execution time vs number of vertices of random graphs for different probabilities is stored in 'results' directory. Refer Problem statement file for detailed information.
The program when run requests the user to input the number of vertices and the name of file from which graph has to be extracted. The graph has to be stored in 'graphs' folder and has to be stored in edge list format. On successful extraction, an undirected graph with the specified number of vertices and edges will be created. This program calculates the betweenness centrality values using Floyd Warshall algorithm as well as n-BFS algorithm. The BC_mat_FW and BC_mat_BFS arrays are updated with the betweenness centrality values of vertices after BC_Floyd_Warshall() and BC_BFS() calls respectively. Both the functions return the time taken for execution of the algorithm. The user is given the option to either print the betweenness centrality values on screen or store it to a file in 'results' directory.
This project was built with
- C
- Ubuntu 18.04.1
- gcc version 7.4.0
Clone the repository into a local machine using
git clone https://github.com/vineeths96/Betweenness-centrality
Open the terminal, make the program and run it.
make
./a.out
Enter the values from the file (or custom values) as requested during execution of the program.
The graphs folder contains the 5 test cases. Provide the file name of graph during execution.
Distributed under the MIT License. See LICENSE
for more information.
Vineeth S - vs96codes@gmail.com
Project Link: https://github.com/vineeths96/Betweenness-centrality