The Birthday Party Problem

Next Tuesday is my happy birthday. As of now, I’m not planning to have a party. And based on some deep graph theoretic analysis that the wife and I just did over the last hour, it’s unlikely I will – for forming a coherent set of people to invite is an NP-hard problem, it seems like.

So five birthdays back we had a party, organised by the wife and meant as a surprise to me. On all counts it seemed like a great party. Except that the guests decided to divide themselves into one large clique and one smaller clique (of 2 people), leaving me as the cut vertex trying to bridge these cliques. That meant the onus was on me to make sure the tiny clique felt included in the party, and it wasn’t a lot of fun.

The problem is this – how do you invite a subset of friends for a party so that intervention by the host to keep guests entertained is minimised?

Let’s try and model this. Assume your friends network can be represented by an unweighted undirected graph, with a pair of friends being connected by an edge if they know (and get along with) each other already. Also assume you have full information about this graph (not always necessary).

The problem lies in selecting a subgraph of this graph such that you can be confident that it won’t break into smaller pieces (since that will mean you bonding with each such sub-group), and no guest feels left out (since the onus of making them comfortable will fall on you).

whatsapp-image-2016-11-28-at-6-53-04-pm

Firstly, the subgraph needs to be connected. Then, we can safely eliminate all guests who have degree of either zero or one (former is obvious, latter since they’ll be too needy on their only friend). In fact, we can impose a condition that each guest should have a minimum degree of two even in the subgraph.

Then we need to impose conditions on a group in the party breaking away. We can assume that for a group of people to break away, they need to be a clique (it is not a robust requirement, since you and someone you find at a party can suddenly decide to find a room, but reasonable enough).

We can also assume that for a group to break away, the strength of their mutual connections should outweigh the strength of their connections to the rest of the group. Since we’re using unweighted graphs here, we can simply assume that a group can break away if the number of edges between this group and the rest of the network is less than the size of the group.

So if there is a group of three who, put together, have two connections to the rest of the group, the group can break away. Similarly, a clique of four will break away from the main group if they have three or less edges going over. And let’s assume that the host is not a part of this subgroup of guests.

Given these constraints, and constraints on party size (minimum and maximum number of guests to invite), how can we identify an appropriate subset of friends to invite for the party? And I’m assuming this problem is NP-Hard (without thinking too much about it) – so can we think of a good heuristic to solve this problem

Do let me know the answer before next Tuesday, else I may not be able to have a party this time as well!

My tryst with Kannada media

So about a month or so back, I wrote up an essay on why the much-maligned TenderSURE project is a right step in the development of Bangalore, and why the Chief Minister’s comments on the issue were misguided and wrong.

Having written it, considering it worthy of a better forum than NED, I shared it with my Takshashila colleagues. They opined that is should get published in a Kannada newspaper, and Varun Shenoy duly translated the piece into Kannada. And then the story began.

We sent it to PrajaVani (which has published several other Op-Eds from other Takshashila people), but they summarily rejected this without giving reasons. We then sent it to UdayaVani, reaching it after passing some hoops, but then they raised some questions with the content, the answers to which had been made quite clear within the text.

I think Mint has spoilt me, in that I assume that it’s okay to write geeky stuff and have it accepted for publication. Rather, it is possible that they’ve recruited me so that they can further bolster their geek quotient. Last week, for example, I sent a piece on Fractional Brownian Motion, and it got published. A couple of years back I’d sent a formula with Tchebyshev’s inequality to be included in a piece on sampling, and they had published that too.

When translating my piece, Varun thought it was too geeky and technical, and he made an attempt to tone it down during his translation. And the translation wasn’t easy – for we had to find Kannada equivalents for some technical terms that I’d used. In some cases, Varun expertly found terms. In others, we simply toned it down.

Having toned down the piece and made an effort to make it “accessible”, UdayaVani’s response was a bit of a dampener for us – and it resulted in a severe bout of NED. And so we sat on the piece. And continued to put NED.

Finally, Varun got out of it and published it on the Takshashila blog (!!). The original piece I’d written is here:

A feature of Bangalore traffic, given the nature of the road network, is that bottlenecks are usually at the intersections, and not at the roads. As a consequence, irrespective of how much we widen the roads, the intersections will continue to constrain the flow of traffic in the city. In other words, making roads narrower will not have a material impact on the throughput of traffic in the city.

And Varun’s translation is here:

(Update: I tried to extract Varun’s piece here but it’s not rendering properly, so please click through and read on the Logos blog)

Read the whole thing, whichever piece you can understand. I think we are on to something here.

And on that note, it might make sense to do a more rigorous network-level analysis of Bangalore’s roads. Designing the graph is simple – each intersection (however small it might be) is a node, each “road segment” is an edge. The graph is both directed (to take care of one-ways) and weighted (to indicate width of roads).

We’ll need data on flows, though. If we can get comprehensive data of origin and destination of a large number of people, we should be able to impute flows in each segment based on that.

And then we can rigorously test the hypothesis (I admit that it’s still only a hypothesis) that bottlenecks on Bangalore’s roads are intersections and not roads.

What makes a Gencu successful?

Last evening I participated in a gencu with Cueballs and Zulu. First of all, let me explain what “gencu” is. It’s a term coined by the wife, and is short for “general catch up”. The reason she coined it was that for a while I was meeting so many people without any real agenda (I still do. Did four such meetings yesterday including the aforementioned) that she felt it deserves its own coinage.

So she would ask “what are you doing today?”. “Meeting this person”, I would respond. “Why?” would be the obvious next question. “No specific reason. Gen catch up”, I would respond.

I ended up saying “Gen catch up” so many times that she decided to shorten it to “gencu”, and we use the term fairly often now. This is the first attempt at publicising it, though. And no, unlike me, she still doesn’t do too many gencus.

So the thing with gencus is that you have no specific agenda, so if you don’t have anything to talk about, or don’t find each other particularly interesting, the meeting can quickly unravel. You can soon run out of things to talk about, and quickly you will start discussing who you are in touch with. So in that sense, gencus can have a high chance of failure (especially if you are meeting the counterparty for the first time or after a long time), and this is one of the reasons why the wife doesn’t do gencus.

One way of insuring against gencus going bad is to have more players. When you have three people, the chances of the gencu going bad are reduced (can’t be ruled out, but the probability decreases). In that sense, you get to meet two people at the same time with the insurance that you will not get bored. On the downside, if there is something specific that two of you want to talk about, you either have to shelve it or let the third person get bored.

While riding to another gencu after the one with Cueballs and Zulu (I must mention that none of the three of us felt the need for a third person to “insure” the gencu. Those two were planning a gencu openly on twitter and since I wanted to meet them both, I invited myself, that’s all!), I was thinking of what can make a multiparty (> 2) gencu successful. I was thinking of my recent multiparty gencus, and most of them had been pleasant and enjoyable, and never boring for any party.

The key to making a multiparty gencu successful, I realised, is mutual respect (ok I’m globing now, I admit). I’ve been through bad 3-way gencus too, and the problem with those has been that two of the three dominate, and don’t let the third person speak (a group discussion like atmosphere). Or two of three have a common interest or connection and speak too much about that, excluding the third person. Such meetings might be okay for one or two parties (among those that are dominating) but definitely uncomfortable for the third.

The above point had two people dominating the gencu at the cost of the third being a problem. Sometimes you don’t even need two people for that. One of the three people can simply hijack the whole thing by talking about themselves, or their pet topic, at the exclusion of the other two people (such people don’t really need counterparties for conversation, but still choose to attend multiparty gencus).

The network structure before the meeting is also important. In our case yesterday, we knew each other “pair-wise”, so it was a complete graph at the beginning of the meeting itself. Not all three-party gencus are like this, and it is possible for two people at one such gencu to not know each other before. This can occasionally be troublesome, since the law of transitivity doesn’t hold for people getting along with or liking people, so if A knows B and B knows C, there is no guarantee that A will get along with C. It can also happen that B will give more importance to talking to A than to talking to C (been affected by this from all three sides in the past). It might be hard to find stuff that everyone finds interesting, resulting in leaving out people. And so forth.

What about larger groups? Groups of five or bigger I’ve seen usually devolving into smaller groups (a notable exception was this one drinking session in late January, where we were 7 people and still had only one (excellent) conversation going), so they need not be analysed separately. Groups of 4 can work, but I prefer groups of 3 (maybe I’ll do a more rigorous analysis of this in a later post).

So what’s your experience with Gencus? What is the ideal number, and how do you go about it?

Graphing social networks

When I’m meeting a random bunch of people I like to graph out social networks in terms of who knew whom before the meeting happened. For example, I was meeting some friends yesterday – B was in town, and wanted to meet people. He called A and C, who got along D (also known to B). After this meeting B was supposed to meet E, but E landed up anyhow. Based on who knew whom before the meeting this is how the network topology went. People are represented by vertices and if there’s an edge between them that means they know each other.

socialnetwork1So it started with A and B meeting, with C supposed to land up in a while. Now, C knows A and B through two different “affiliation groups”, but knows both quite well. So C lands up, but now the question is what do you talk about. The basic structure of the group – where A-B, B-C and C-A know each other through three separate affiliation groups means you can’t talk about people (thankfully!).

Anyway conversation goes on, and then D lands up. When B asked C if they could meet, he said “I’m not in touch with anyone else here in Bangalore. But if you think there’s someone else from our affiliation group who’s here and wants to meet, bring them along”. Thus, C invites D (whom he hasn’t met for ages) and D lands up.

Now, for the first time,  the group is not a clique – since A and D don’t know each other. It’s up to B and C now to control the conversation in a way that A or D don’t get bored. People talk about work, careers and all that – where anyone can give gyaan.

After a while, E lands up. Now, E doesn’t know anyone else in the group (apart from B). So now, B becomes a cut-vertex. B starts talking to E. With B and E taken out, in the A-C-D network, C is now a cut-vertex! So it’s up to C to manage the conversation with A and D! C isn’t particularly good at that!

Soon A leaves. Now, the group effectively splits, while sitting at the same table. B talks to E (no one else knows E), and C talks to D. All is well.

The problem with the group was that none of the “connectors” (B, C) were particularly good at connecting people, and keeping one conversation. This, though, wasn’t the case at a drinks session I attended on Monday evening. There, the social network at the beginning of the conversation looked like this (variables here all mean different people, only I was common to both meetings):

socialnetwork2

The thin lines here indicate that B-F and E-F had met before, but didn’t know each other well enough. As you can see, A is now the cut-vertex here. The difference, though, is that A is a master networker, and has a self-professed interest in “collecting interesting people”. The group for the meeting was also fully curated by A – no one “brought along” anyone else.

So A ensured that the conversation flowed. He made sure people connected, and there was great conversation. At the end of the day the network was a clique!

I’ve never been good at making these connections. I dread gathering where I’m the cut-vertex – forever afraid that someone might be left out. Connecting and collecting people is surely a skill I need to develop!

PS: At a coffee shop in Mumbai eight summers ago, I was at one end of the social network which looked like this. Don’t ask me how it came about!

socialnetwork3

Reforming Bangalore’s Public Transport Network

This is based on a twitter rant on the same subject a few weeks back.

Bangalore’s public transport network has traditionally followed a hub-and-spoke model, with three hubs – Kempegowda Bus Station (aka “Majestic”), KR Market and Shivajinagar. It can be modeled, however, as a two-hub system, for Majestic and Market are quite close to each other and thus quite well-connected. It was probably not originally meant to be that way – for bus number 1 (not sure it still exists) ran from Jayanagar 4th Block to Yeshwantpur – basically from the south to the north-west corner of the city. Of course, it passed through Market.

Over time, however, the bus system has moved to an increasingly hub-and-spoke model. The BMTC (Bangalore Metropolitan Transport Corporation) did one exercise a few years back, trying to rationalize routes (it was partly due to an effort led by Ashwin Mahesh of Mapunity). However, while adding useful additions such as the ring routes (the “big circle” and the “chikka (small) circle” routes) and one or two “trunk routes” (that run right across town), what this revised template does is to further increase the primacy of the hubs. For example, the much talked about Big 10 routes are essentially arterial routes running from a point in the middle of town to some place along one of the highways leading out of Bangalore (they are not strictly hub routes, though, since some of them stop a short distance from a major hub).

The increase in primacy of hubs combined with metro construction (the two metro lines will criss-cross each othe at – you guessed it – Majestic!) has completely overwhelmed the hubs. It is impossible (unless you sacrifice copious amounts of time) to change buses at Majestic now, for the amount of time it takes for a bus to get into majestic and for a bus to get out of majestic is too high a transaction cost.

Moreover, changing buses at a terminus is not efficient, given the waiting times involved and the extra transaction costs of getting out of the terminus. What works better is changing buses at an intermediate stop. To use an anecdote, for two years (1998-2000) I traveled to school in Indiranagar (east Bangalore) from my home in Jayanagar (south Bangalore). I would take a bus going to Shivajinagar (Jayanagar-Shivajinagar is well connected – being a hub route) and get off at Richmond circle, from where I would take a bus from Majestic to Indiranagar (again a hub route, so well served). I could change buses while standing at the same bus stop (made things easier), and the frequency of buses on the two hub routes meant I would get to school easily (again the traffic in the 1990s was nothing compared to what it is now). I had the option of changing buses at a hub, but eschewed it due to transaction costs.

Coming back, what we need in Bangalore is to reformat the bus network in a way that mimics the patterns in which people travel. Right now the assumption of the BMTC seems to be that they should connect every area to a major hub, and then let people take it from there. What they do not take into account is that 1. traffic has grown much worse and 2. People put a higher value on their time nowadays, because of which the transaction cost of the old hub-and-spoke model is way too high. What they need to do instead is to design the network based on people flows.

The first step of such reform is to understand the patterns in which Bangalore moves. One way to do this would be via smart ticketing. A few years back buses in Bangalore started introducing smart ticketing machines, and your ticket would be a printout. However, that didn’t take off. If that can be reintroduced (in all buses) and coupled with destination based ticketing rather than leg based ticketing (for example, if I’m going from Jayanagar to Indiranagar via Richmond Circle I get on to the bus in Jayanagar and buy a ticket to Indiranagar directly. The same ticket allows me to travel on any bus between Richmond Circle and Indiranagar. This introduces complexity but can be done). This will give the BMTC information in terms of the routes on which people actually travel. And once that happens, an effort can be made to reformat the bus network.