The concept of Social Graph was introduced by M. Zuckerberg at the first Facebook F8 conference in 2007 when he introduced the Facebook platform to model relationships among internet users.
Consider the attached file Graph.java (a link to this file is provided below for downloading purposes) which defines a generic undirected Graph class. Design and implement a class SocialGraph (in a separate source file SocialGraph.java) which extends the class Graph. In a social graph, the vertices (graph nodes) represent people names while the un-directed edges represent the acquaintance relationships between them. Class SocialGraph should define constructor(s) and enhance the behavior of the class Graph by defining the following social graphs’ specific methods:
degree(v) / (n-1)
where degree(v) represents the number of vertex incident edges and n represents the number of graph vertices. For social graphs, a high degree of centrality for a person v reflects his/her dominant position in the group or his/her social interaction skills.
foreach pair of vertices (p, q) in AdjacencyList(v)
if (p, q) is in E then add 1 to triangles[v]
A triangle should be specified by its vertices.
[(number of edges connecting v’s neighbor vertices) / (number of edges, potentially connecting v’s neighbor vertices)] * 100
– the number of edges connecting v’s neighbor vertices is calculated as:
(number of triangles incident to vertex v)
– the number of edges, potentially connecting v’s neighbor vertices is calculated as:
[degree(v) * (degree(v) – 1)] / 2
For social graphs this value measures of how close wrapped are the persons in the social graph around the given person.
(1 / n) * ∑ clusterIndividual (v)
This value indicates the overall density of the social graph.
Your SocialGraph class should compile without errors.
Design and implement a driver program TestSocialGraph (in a separate source file TestSocialGraph.java) for testing the methods implemented in Part 1. The driver program should build a social graph from an input file data.txt. After building the social graph, in a loop, the program should invite the user to select for execution one of the following operations: (1) normalizedDegreeOfCentrality, (2) numberOfTrianglesIncidentToVertex, (3) listOfTrianglesIncidentToVertex, (4) clusterIndividual, (5) averageClustering, (6) isIndirectAcquaintance, (7) addVertex, (8) addEdge, (9) printEdges and (0) exit the loop and the program.
As a result of each operation execution, relevant information should be displayed to the user. For example, as a result of invoking clusterIndividual method, the cluster individual value for the given person should be displayed.
The programs should compile without errors.
2. If an operation requires additional information, the user will be prompted to enter it.
3. The input file (a simple .txt file) should be generated by the students using a simple text editor such as Notepad.
4. Person names (instead of indices) should be used in I/O operations involved by the user interface.
2. The solution description document <YourSecondName>_P3 (.pdf or .doc / .docx) containing:
(2.1) assumptions, main design decisions, error handling, (2.2) test plan, test cases and two relevant screenshots, (2.3) the table of average execution time filled in with the measure values. (2.4) discussion of the results, (2.5) lessons learned and (2.6) possible improvements. The size of the document file (including the screenshots) should be of three pages, single spaced, font size 12.