|Due By (Pacific Time)
||12/07/2016 12:00 am
This is an open-ended homework requiring a bit of creativity.
Imagine a random graph that has 2n nodes that is formed by two communities of n nodes each. Within each community every edge appears independently with probability p. Between the two communities every edge appears with probability q. For example is p = 0 and q = 1, this is just the complete bipartite graph on 2n nodes. On the other hand if p=1 and q=0 then this graph has two components, each one a complete graph on n nodes. If p = 0.99 and q=0.01 then it will not be disconnected, but will still look like two densely connected parts with hardly any edges connecting the two sides.
- The goal of this homework is to write a matlab function that takes as input the adjacency matrix of the graph on 2n nodes, and returns a list of nodes in one of the communities.
- Of course, since the graph is random, this task cannot be achieved perfectly all the time. Any algorithm will be prone to make mistakes. The bigger the difference between p and q is, the easier the task becomes. For example when q =0 you can just find the connected components. This, however, will not work for q slightly bigger than 0.
- You can assume that p is much bigger than q. A good test case is when p=0.9, q=0.1.
You don't have to find the "best" solution. There is no best solution. All you need to do is try. Think about possible ways how you would accomplish the task, and try to write code based on that. Try to make your approach as elementary as possible (do not use any built-inmatlab function that is designed for a similar purpose). You are allowed to use, possibly in a modified form, my "official" solutions to the previous computer homework.
Attached is a matlab function file that generates such a random graph. It takes 3 parameters: n,p,q, and returns 3 items: the adjacency matrix, and the list of nodes in the two communities. (This is only so that you can compare your own solutions to the actual communities hidden in the graph.)