A social network can be represented as a graph, G. A clique is a set of vertices

Question

A social network can be represented as a graph, G. A clique is a set of vertices {v1,···,vk} such that for any pair of vertices a and b in this set, (a,b) is an edge. The size of a clique is the number of vertices in the set. Write a Python program that ?nds a maximum clique.

Figure 1: There are cliques with 1, 2, 3, and 4 vertices. {Ellen,Frank,Bob} is not a clique because there is no edge between Ellen and Bob. {Ellen,Abe,George} is a clique with 3 vertices. {Abe,Bob,Carol,Dale}is a maximum clique with 4 vertices. There can be more than one maximum cliques.

Explanation / Answer

I used networkx to draw the graph.

The plan is done as per the below:

a) find maximal cliques (just in case, maximal cliques are not necessary the largest cliques);
b) draw the graph and remember the coordinates of vertices that were used by drawing programm;
c) take clique's coordinates, calculate the center and radius of the cirles that surrounds it;
d) draw the circles and color the verteces of the cliques in the same color (for the verteces in the intersection of 2 and more maxcliques it's not possible).

Python Program:

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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