An application of graphs | Computer Science homework help


Social Graphs

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

Consider the attached file (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 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:

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

isAcquaintance determines whether two persons supplied as parameters can establish social contact direct or 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 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.

An example of the data input file content, its format and the corresponding social graph layout is shown in the attached file SocialGraph_Example.pdf.

The programs should compile without errors.


1. You may consider that there are no errors in the input file structure.
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.

Submission Requirements

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

1. All .java source files and the input file(s).

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.



US Custom Writers
Calculate your paper price
Pages (550 words)
Approximate price: -

Why Work with Us

Top Quality and Well-Researched Papers

We always make sure that writers follow all your instructions precisely. You can choose your academic level: high school, college/university or professional, and we will assign a writer who has a respective degree.

Professional and Experienced Academic Writers

We have a team of professional writers with experience in academic and business writing. Many are native speakers and able to perform any task for which you need help.

Free Unlimited Revisions

If you think we missed something, send your order for a free revision. You have 10 days to submit the order for review after you have received the final document. You can do this yourself after logging into your personal account or by contacting our support.

Prompt Delivery and 100% Money-Back-Guarantee

All papers are always delivered on time. In case we need more time to master your paper, we may contact you regarding the deadline extension. In case you cannot provide us with more time, a 100% refund is guaranteed.

Original & Confidential

We use several writing tools checks to ensure that all documents you receive are free from plagiarism. Our editors carefully review all quotations in the text. We also promise maximum confidentiality in all of our services.

24/7 Customer Support

Our support agents are available 24 hours a day 7 days a week and committed to providing you with the best customer experience. Get in touch whenever you need any assistance.

Try it now!

Calculate the price of your order

Total price:

How it works?

Follow these simple steps to get your paper done

Place your order

Fill in the order form and provide all details of your assignment.

Proceed with the payment

Choose the payment system that suits you most.

Receive the final file

Once your paper is ready, we will email it to you.

Our Services

No need to work on your paper at night. Sleep tight, we will cover your back. We offer all kinds of writing services.


Essay Writing Service

No matter what kind of academic paper you need and how urgent you need it, you are welcome to choose your academic level and the type of your paper at an affordable price. We take care of all your paper needs and give a 24/7 customer care support system.


Admission Essays & Business Writing Help

An admission essay is an essay or other written statement by a candidate, often a potential student enrolling in a college, university, or graduate school. You can be rest assurred that through our service we will write the best admission essay for you.


Editing Support

Our academic writers and editors make the necessary changes to your paper so that it is polished. We also format your document by correctly quoting the sources and creating reference lists in the formats APA, Harvard, MLA, Chicago / Turabian.


Revision Support

If you think your paper could be improved, you can request a review. In this case, your paper will be checked by the writer or assigned to an editor. You can use this option as many times as you see fit. This is free because we want you to be completely satisfied with the service offered.