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.io.FileReader;
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.TimerTask;
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
			set.add(new Integer(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 {
		BufferedReader r = null;
		String line = null;
		try {
			r = new BufferedReader(new FileReader(f));
			while(null != (line = r.readLine())){
				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();
			}
		}

		//add to the nodeSet
		nodeSet.addAll(nodeMap.keySet());

	}

	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);
		}

		n1.connections.add(n2.id);
		n2.connections.add(n1.id);
	}

	class Node {
		Integer id;
		TreeSet connections;
	}

	public static void main(String[] args) throws Exception {
		final AllClique app = new AllClique();
		app.readInput(new File(args[0]));
		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.