Design and implement the SocialGraph class for representing and processing socia

Question

Design and implement the SocialGraph class for representing and processing social graphs, by extending the abstract class AbstractGraph. 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

Explanation / Answer

http://notforcheating.com

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.