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.

Advertisements

Published by

Bobby Corpus

Is an IT Architect.

One thought on “Finding the cliques of my Facebook friends”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s