[Solved] CS3353 Project 02 Link Searching and Community Discovery

5/5 – (1 vote)

Overview

Assume you have a graph that represents some type of relationship between two people. For example, it could represent friendship in a social network like Facebook. Or it could represent co-authorship of a paper, article, or book. In these examples, we are considering the edges to be undirected. However, in social networks that have a follow-type relationship between two individuals, the edges would be directed. Youll implement a set of algorithms related to searching the graph and community discovery.

Example network input:

[7]ABCDEFG[undirected]A - BA - CB - CB - DD - GD - FD - EG - FE - F

Youll read in a control file that will contain a set of commands to be processed by your project.

• or Open a file for reading. Takes one argument the file name.
• ex: or g1.txt
• ow set the output file. Takes one argument the name of the file.
• ex: ow g1-output.txt
• dfs Depth first search. Takes one argument the start node.
• ex: dfs E
• Output: To come
• bfs Breadth first search. Takes one argument the start node.
• ex: bfs G
• Output: To come
• mc Make a Connection with the smallest number of introductions. Takes two arguments the two people to attempt to connect.
• ex: mc A D
• Output: A set of introductions that need to be made in order for person A to be introduced to person D.
  • Ex: {(A - B), (B - D)}
• dc Discover Communities. No arguments. Implement the Girvan-Newman algorithm a set of reasonably well connected communities. You will define reasonably.
• Output: a set of communities, each community identified by its members presented in alphabetic order.
• Additional Resources on Girvan-Newman Algorithm:
  • Chapter 10 Section 2 of Mining Massive Data Sets
  • Social and Information Network Analysis Course Slide Deck 14
  • Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 78217826 (2002).