RYB Colorspace and Readable Palettes

April 12, 2012

I’m currently in the midst of writing my PhD thesis but I am still working on some other projects at the same time. Lately, we’ve been developing with my intern a new graph visualization algorithm. It’s not yet ready for prime time but I can at least say that the focus of the layout is to make social communities pop out. Although the layout itself does a great job at grouping cohesive communities in a tight spatial region, we wanted to go further and add some colors – and anyways, colors are nice. Now the problem is that there can be a large number of groups, and therefore a large number of colors. We had to find a way to avoid any clashes – colors which are too similar to be distinguishable to the naked eye.

So I started thinking about it and I remembered that I had read a paper on the RYB colorspace a couple of years ago. There are two things I like about this color model. First, it’s what I learned when I was a kid and that I played with paint: blue + yellow = green, and not blue + green = yellow as in RGB. The second very nice thing is that, and this is mostly coincidental I suppose, is that the RYB colors of the form a/k, b/k, c/k turn out to be usually pretty and vivid for small values of n. This means that its possible to evenly distribute in the colorspace colors which look nice and do not look alike.

I’ve implemented these ideas into a javascript webapp (source). Behind the scenes, two things happen. First we generate the colors and then those colors are sorted by their distance to the average of all previous colors, in order to guarantee that the first colors are always different enough. Feel free to fork/path/pull request or suggest any enhancements.

Who did I forget

January 26, 2012

Yesterday was an amazing day, I finally launched who did I forget, an app which allows a user to easily create a guest list for an event by entering a rough sketch of who they’d like to see there.

For the past two years I’ve been working as part of my PhD on the notion of social groups1. We all belong to several groups: family, friends, co-workers, poker group, college buddies, etc. and this notion of group is pretty well understood. However, there was no formal and quantitative way of describing a social group. Last year, I came up with the cohesion, a metric which allows just that2. You can think of it as an analog to Google’s Pagerank or Facebook’s Edgerank except we are not rating web pages or connections betweek persons but what holds a group of people together3.

Social networks have a feature called triadic closure: if Alice and Bob know each other, and Alice and Chuck know each other too, then there is a very high probability that Bob and Chuck know each other. Of course, this does not happen all the time, I believe for the simple reason that this property only holds if the type of link between the individuals is of same nature. If Alice and Bob are part of the same family, and Alice works with Chuck, then we can’t say anything, right?

On Facebook, for example, you only have friends, but reality is a lot more nuanced. Using triads (three people who are all connected to each other) instead of simple connections in the Cohesion allows us to filter out different types of relationships.

At the beginning of last year, I launched Fellows in order to validate this intuition, and the results were astounding. We asked people to give a rating to groups of people and then compared those ratings to the cohesion. There was a extremely high correlation between the two values. This means that at last we have a quantitative way of defining what a social group is: a set of people with high cohesion.

Without going into gory details, I came up with an algorithm4 which expands a given group of people into a highly cohesive group. Who did I forget is built around this algorithm. When the user enters a list of guest, we first construct the graph of who knows who among the user’s Facebook friends, and we then iteratively expand around each guest in order for him to be part of a cohesive group in the output guest list.

I hope this gives more insight into how who did I forget works. My next article will be a more in-depth explanation of the actual implementation.

  1. Also called social communities, but I find that the term communities has a broader meaning in real life, which differs from the one it has in Social Network Analysis. The notion of communities or groups relates to the structure of the network, whereas the common acceptation of the term is more semantic, e.g. communities of interests.↩

  2. Triangles to Capture Social Cohesion A. Friggeri et al. Third IEEE International Conference on Social Computing, Oct 2011, MIT, Cambridge, United States.↩

  3. Of course, only the aim of the metric is similar, the cohesion works in a very different way.↩

  4. COVER, currently unpublished.↩

Maximizing the Cohesion is NP-hard

September 12, 2011

At the beginning of the year, I introduced the cohesion, a new graph metric which I believed captured the communityness of a subset of a network. My intuition was confirmed by Fellows, as the results lead to the conclusion that the cohesion is highly correlated to user subjective perception of communities.

The question then remained: given a network is it possible to find its subset of nodes of maximum cohesion?1

Well, this is solved now, I’ve just shown – and this was not easy – that this problem is NP-hard. I won’t go into the technicalities of the proof, but those interested may want to take a look at the research report available at [arXiv:1109.1994v1].

In layman’s terms, this means that if you organize a party, it’s algorithmically hard to find who to invite in order to maximize their sense of belonging to a community. So, next time you’ll wonder if you should send a invite to your in-laws, you’ll have an excuse.

  1. Or more specifically, the related problem with a constraint on vertices which must belong to the subset.↩

Jump: Alfred-like cd

September 4, 2011

One app I can’t live without on my mac is Alfred. Unfortunately, Alfred is only useful in a GUI environment. My day at work often starts like this:

⌘␣ term ↵
cd Doc[TAB]...[TAB]...[TAB]

A couple of days ago, the thought crossed my mind that there ought to be a better way of handling this, and I’m now introducing jump. First note that jump relies on mdfind – i.e. spotlight – and has only been tested on OSX Lion and requires node.js. Without further ado, install with:

npm -g install jump
jump >> ~/.bash_profile
source ~/.bash_profile

To use jump, type j in a terminal, and enter your query at the prompt: results will be updated live as you type. Switch between suggestions with up and down arrow, select with enter and boom you’re in the right directory. Basically, all the fancy web 2.0 autosuggest mojo right in your terminal. The code is of course available on github.

Hello World

August 1, 2011

A couple years back, I used to maintain a blog at this same address, which I shut down for the two usual reasons: I had mostly nothing to write, and it was time consuming. Since launching Fellows six months ago, I have been having a growing need to once again be able to express myself and share my thoughts online.

In the last two months, Google launched their social network with an emphasis on social groups, Facebook has for the most part ignored Fellows, and a few companies started focusing on community detection. A few times I felt the urge to comment or reply to several stories but lacked the place to do so.

Moreover, as an academic, there are subjective ideas such as musings and rants about Social Network Analysis that I just cannot dump into an article and hope getting published some day.

Hence this blog, which is destined to serve as a receptacle to my thoughts on social networks, their use and their analysis.