Social Graphs - An Application of Graphs

Specification

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.

Part 1

Design and implement the SocialGraph class for representing and processing social graphs, by extending the abstract class AbstractGraph (Liang, Listing 30.3). In a social graph, the vertices (graph nodes) represent people (identified by their names) while the un-directed edges represent the acquaintance relationships between them. Consider the implementation of the following specific methods:

• isConnected, tests whether the social graph is connected or not. If a social graph is connected, any person p can be accessed by any other person q or, in other words, there is a path from vertex q to vertex p.
• normalizedDegreeOfCentrality calculates and returns the normalized degree of centrality for a given vertex v. The required value is calculated as: 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.
• numberOfTrianglesIncidentToVertex, calculates and returns the number of triangles incident to vertex v. The algorithm below calculates the number of triangles incident to all graph vertices (V is the set of vertices, E is the set of edges):

foreach v in V
foreach pair of vertices (p, q) in AdjacencyList(v)
if (p, q) is in E then add 1 to triangles[v]

• listOfTrianglesIncidentToVertex calculates and returns the list of triangles incident to vertex v. A triangle should be specified by its vertices.
• clusterIndividual for a given vertex v, calculates and returns the percentage indicating how close its neighbors are to make a complete graph and is calculated as: [(number of edges connecting v's neighbor vertices) / (number of edges, potentially connecting v's neighbor vertices)] * 100 where:
  • 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.
• averageClustering for the social graph, calculated as (the sum applies to all vertices v in V): (1 / n) * Σ clusterIndividual (v) This value indicates the overall density of the social graph.
• addVertexAndEdges for adding a vertex and the associated edges to an existing social graph.
• depthFirstSearch and breadthFirstSearch representing the depth-first search, respectively breadth-first search, each returning the list of vertices as a result of graph traversal.

Part 2

Design and implement a driver program TestSocialGraph and the test cases for testing the methods implemented in Part 1. The driver program should build a social graph from an input file. After building the social graph, in a loop, the program should invite the user to select for execution one of the following operations: (1) isConnected, (2) normalizedDegreeOfCentrality, (3) numberOfTrianglesIncidentToVertex, (4) listOfTrianglesIncidentToVertex, (5) clusterIndividual, (6) averageClustering, (7) addVertexAndEdges, (8) breadthFirstSearch, (9) depthFirstSearch and (0) exit the loop and the program.

As a result of execution, each operation should display relevant information to the user. For example, after the execution of depthFirstSearch and breadthFirstSearch operations, the list of vertices (person names) generated as the result of graph traversal should be displayed to the console, or as a result of invoking clusterIndividual method, the cluster individual value for the given person should be displayed.

An example of input file content and the corresponding social graph layout is shown in the example below. The sequence of person names in the first part of the file (until the # separator) defines the vertices whiles the last part of the file (after the # separator) defines for each vertex (represented by its index in the sequence, starting from index 0) its associated adjacent vertices.

Notes

• You may consider that there are no errors in the input file structure.
• Additional graph related methods could be defined (or re-used) as necessary.
• If an operation requires additional information, the user will be prompted to enter it.
• Person names (instead of indices) should be used in I/O operations involved by the user interface.