Description

Help Protect the City
1 Background
Let G = (V,E) be a simple, unweighted, undirected graph. The distance between two vertices u,v ∈ V , given by d(u,v), is defined as the length of the shortest path between u and v in the graph G. Note that d(u,u) = 0.
The farness of a vertex u in a graph G is defined as:
far(u) = X d(u,v)
v∈V
The closeness centrality of u is then defined as:
1 CC(u) = far(u)
2 Problem
Your TAs have been working hard helping Batman connect his cell phone audio player to bluetooth on his batmobile, so we are turning to you for help with this problem.
(1)
Your job is to design, analyze, and implement an algorithm to efficiently compute the heist-closeness centrality for each vertex in a graph.
Concretely, you need to do the following:
1. Design an algorithm to compute the heist-closeness centrality, as defined by (1). Write thehigh-level idea, then concrete details and pseudo-code for the algorithm.
2. Prove the feasibility of the algorithm. That is, prove that the algorithm will correctly computethe heist-closeness centrality for each vertex.
3. Compute and prove the run-time and space complexity of the algorithm. Identify if differentdata structures will impact the complexity.
4. Using one of the provided templates, implement your new algorithm and ensure it runscorrectly on the sample graphs provided.
3 I/O File Formats
There are three file formats used for this assignment which are described in this section.
3.1 Graph File Format
The input graph files are in a format that is easy to construct a CSR from. The file extension used is .graph. The format is as follows:
n m s1 d1 s2 d2
… sm dm
The edges must be sorted numerically by source.
3.2 Heist Nodes File Format
The file extension .h is used for heist nodes. The heist nodes are provided in the following format:
k v1 v2 … vk
Here, k is the number of heist nodes, or k = |H|. Each following vi is a given vertex ID that is a heist node. The values should be formatted as ASCII integers.
3.3 Output File Format
The output file format has an extension of .hc and is as follows:
n v1-hcc v2-hcc … vn-hcc
Here, n is n = |V |, as in the input graph format. Each following line corresponds to the respective vertex’s computed CHC value. The values should be formatted as an ASCII integer and doubles respectively.
Please follow these instructions carefully.
• You should submit two files:
1. A PDF containing your typed written assignment: the algorithm, the feasibility proof,the run-time and space complexity analysis and proof, and the implementation report and evaluation.
2. A single source code file (C++, Python, or Java) that implements your algorithm andcompiles or runs in the templates provided at https://github.gatech.edu/ucatalyurek7/cse6140-Fall18.git. This file will be used to replace hcc.cpp, HCC.java, or hcc.py appropriately when testing