# Finding the cliques of my Facebook friends

The availability of the facebook graph api made the studying of social interactions much easier. I have seen some social experiments using the data from facebook. For example, you can verify the small world effect or what is known as the six degrees of separation.

I did my own experiments also using the facebook api. What I did was to compute the cliques of my friends. I did this experiment last August of 2009 and this is the only time I’m able to document it. During that time, I was only connected to 82 friends.

What is a CLIQUE? A clique is a group of people who are mutual friends with each other. In the facebook setting, if 5 people are mutual friends, they form a clique. In this experiment, I computed the maximal cliques contained in my set of friends. A maximal clique is the maximum number of friends who are mutually connected with each other. Why study cliques? Cliques allow you to determine the interest of a person just by studying the group he/she belongs to. As the saying goes, birds of the same feather flock together.

To gather my data, I used the facebook api to get a list of my friends, and for each friend I queried the facebook function friends.areFriends by passing to this function a list of facebook ids corresponding to my friends. The output is an array of zeroes and ones. A 1 indicates that two people are mutual friends and a 0 indicate that they are not.

Once I gathered my data, I put it in a format that can be read by a program to compute the cliques. Here is a sample of the input file.

``` 0 1
0 2
0 4
0 7
0 10
0 13
0 14
0 15
1 2
1 3
1 7
1 8
1 9
1 10
1 11
1 12
1 14
1 15
1 19
1 22
1 25
2 3
2 4
2 7
2 8
2 10
2 12
2 13
2 14
2 16
```

Let me explain the format. The numbers represent a person id. Each row is composed of two numbers. For example, the row “0 1” can be read as person number 0 is a friend of person 1. The row containing “2 14” can be read as person number 2 is a friend of person 14. I did this for all my friends.

The algorithm I applied to generate the maximal cliques is taken from the book of Donald Kreher and Douglas Stinson entitled “Combinatorial Algorithms: Generation, Enumeration and Search”. The algorithm can be found on page 112 of the book. Below is the java program I wrote to implement the algorithm.

```import java.io.BufferedReader;
import java.io.File;
import java.util.Comparator;
import java.util.Date;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

import com.apple.mrj.macos.carbon.Timer;

public class AllClique {

long startTime = System.currentTimeMillis();

public void allClique(Set NLminusOne, Set CLminusOne, int x , String v){
if( null == NLminusOne ){
System.out.println("[]");
} else {
v += x + " ";
//printVector();
//System.out.println(v);
}

Set NL= null;
if(null == NLminusOne){

NL= (Set) nodeSet.clone();
} else {
Node n = nodeMap.get(x);
if(null !=n){

NL = (Set) n.connections.clone();
intersect( NL , NLminusOne);
}
}

if(null == NL || NL.size() == 0){
//System.out.println("*");
v+="*";
System.err.println(v);
}

System.out.println(v);

Set CL = null;
if( null == CLminusOne ){
CL = (Set) nodeSet.clone();
} else {
Node n= nodeMap.get(new Integer(x));
if(null != n){
CL = (Set) n.connections.clone();
Set BLminusOne = getBL(x);
intersect(CL, BLminusOne, CLminusOne);
}
}

if(null != CL){

if(v.length()> 0){
char c =  v.charAt(v.length() -1);
if(c == '*'){
v = v.substring(0,v.length()-1);
}
}

for(Iterator iter= CL.iterator(); iter.hasNext();){
allClique(NL, CL, iter.next(), v);

}
}
}

public Set getBL(int l){
int max = nodeSet.size();
TreeSet set = new TreeSet();
for(int i=l+1;i
}

return set;
}

public void printVector(int l){
String str="[";
for(int i=0;i
str+= i;
}
str+= "]";

System.out.println(str);
}

public void printVector(Integer[] X){
String str = "[";
for(Integer i: X){
str += i + " ";
}
str += "]";

System.out.println(str);
}

HashMap nodeMap = new HashMap();
TreeSet nodeSet = new TreeSet();

public boolean intersect(Set a, Set b, Set c){
boolean bool = a.retainAll(b);
if(bool){
bool = a.retainAll(c);
}

return bool;
}

public boolean intersect(Set a, Set b){
boolean bool = a.retainAll(b);

return bool;
}

public void readInput(File f) throws Exception {
String line = null;
try {
if(line.startsWith("#")) continue;
StringTokenizer st = new StringTokenizer(line," ");
String sFrom = st.nextToken();
String sTo = st.nextToken();
createConnections(sFrom.trim(),sTo.trim());

}
} finally {
try {
if(null != r){
r.close();
}
}catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
}

}

public void createConnections(String sFrom, String sTo){

System.out.println(sFrom + "--" + sTo);
Node n1 = nodeMap.get(new Integer(sFrom));
if(null == n1){
n1 = new Node();
n1.id = new Integer(sFrom);
n1.connections = new TreeSet();
nodeMap.put(n1.id, n1);

}

Node n2 = nodeMap.get(new Integer(sTo));
if(null == n2){
n2 = new Node();
n2.id = new Integer(sTo);
n2.connections = new TreeSet();
nodeMap.put(n2.id, n2);
}

}

class Node {
Integer id;
TreeSet connections;
}

public static void main(String[] args) throws Exception {
final AllClique app = new AllClique();
for(Iterator iter = app.nodeSet.iterator();iter.hasNext();){
System.out.println("=> " + iter.next());
}

app.allClique(null, null, 0, "");

}
}

```

Running program with my data, I was able to generate the cliques. To visualize the result, a graph drawing application called graphviz came in very handy. Here is the result of the clique computation:

Click on the graphic so that you can zoom on it.