Social Graphs - An Application of Graphs

**1. 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.

*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 for 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.*isIndirectAcquaintance*determines whether two persons supplied as parameters can establish social contact through a chain of transitive acquaintance relationships (in terms of graphs it means that there is a path between the two nodes representing the two persons).

Additional (helper) methods and / or instance variables may be defined as necessary.

Your **SocialGraph** class should compile without errors.

**Part 2**

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. 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.

An example of input file content, its format and the corresponding social graph layout is shown in the attached file **ExampleSocialGraph.pdf **(a link to this file is provided below for downloading purposes).

**Notes**

- You may consider that there are no errors in the input file structure.
- If an operation requires additional information, the user will be prompted to enter it.
- The input file (a simple .txt file) should be generated by the students using a simple text editor such as Notepad.
- Person names (instead of indices) should be used in I/O operations involved by the user interface.

**2. Submission Requirements**

Submit the following before the due date listed in the Calendar:

1. All .**java** source files and the **input file(s).** 2. A document file including relevant screenshots showing program execution as a result of test cases.

3. A document file describing your solution which should include the following elements: (3.1) a short problem analysis, (3.2) main design decisions, (3.3) assumptions, (3.4) short description of classes, (3.5) user interface, (3.6) test plan, (3.7) error handling, (3.8) lessons learned and (3.9) possible future developments. The size of the document should be of 4 pages, single spaced, font size 12.

Subject | Computer |

Due By (Pacific Time) | 10/05/2014 12:00 am |

Tutor | Rating |
---|---|

pallavi Chat Now! |
out of 1971 reviews More.. |

amosmm Chat Now! |
out of 766 reviews More.. |

PhyzKyd Chat Now! |
out of 1164 reviews More.. |

rajdeep77 Chat Now! |
out of 721 reviews More.. |

sctys Chat Now! |
out of 1600 reviews More.. |

sharadgreen Chat Now! |
out of 770 reviews More.. |

topnotcher Chat Now! |
out of 766 reviews More.. |

XXXIAO Chat Now! |
out of 680 reviews More.. |