So the second edition of the NED Talks took place last night. And no, this is not a “match report”. So the purpose of the NED Talks is to put together a bunch of interesting people who are interesting in different ways, and get them to talk. There are approximately ten talks (the first edition had thirteen, the second eight) followed by interaction, and a round of interaction before the event. So in certain ways, NED Talks are networking events.

So the question is what the ideal “network structure” of the networkers is in order to ensure a successful networking session. The idea is that the network at the beginning of the session needs to be only slightly dense – if there are too many people who know each other at the beginning of the session, there is not much of a point in the event as a networking event, for the value add in a networking event is to bring together people who hitherto didn’t know each other, and to strengthen existing weak ties.

The network being not dense enough also is also a problem, for that means that people might be lost. So if you have a lot of people who have never known each other earlier, and if some of them are introverted (as is likely to happen when you put together intelligent people), the conversation can be a bit of a non-starter. So low density is also not a good thing.

Then there is the issue of cliques – if you have a bunch of people who all know each other from earlier, then the others might feel “left out”, and not be able to get into the conversation. There are likely to be “in-jokes” and “in-stories” which everyone else finds irrelevant. I remember being at one such gathering where I was the only person who was not thus “in”, and so I got up and announced that I was getting bored and walked out.

Anyway, so let us represent all attendees to a party or event in the form of a graph (undirected). Each vertex represents an attendee and two attendees are connected by an edge if they know each other from before. Given such a graph, can we construct an algorithm to “verify” if it is a good set of people to have for the party? Oh, and this is one of the insights from yesterday’s NED talks – computational complexity can be measured in terms of how “easy” it is to verify a given solution, rather than generate a new solution.

The first thing you can do is to find the size of the largest clique – if it exceeds a certain proportion (a third maybe? a fourth?) of the total number of attendees, it is a bad idea, for that means that this clique might dominate the conversation.

Then you can calculate the “edge density” of the graph – the total number of edges on the graph to the number of “possible edges” (given by NC2 where N is the number of attendees). For example, the edge density of the first NED Talks was 3/26 (largely due to 5 attendees who were not connected to any other nodes) . The edge density of the second NED Talks was 1/3 (might have been higher but a not-so-well-connected attendee backed out at the last moment). What range of edge density makes sense? Or should we use the variance in edge density also?

Then there is the number of “components” in the graph – if the graph is mostly disconnected, the group might split up into small cliques which might defeat the purpose of the networking event itself and lead to disconnected conversation. Note that nodes of zero degree don’t matter here – it’s components wiht at least two people.

And so forth. So can anyone help me build an algo to “verify” if a party / networking event is going to be good given a graph of who knows who from before?