Order of guests’ arrival

When I’m visiting someone’s house and they have an accessible bookshelf, one of the things I do is to go check out the books they have. There is no particular motivation, but it’s just become a habit. Sometimes it serves as conversation starters (or digressors). Sometimes it helps me understand them better. Most of the time it’s just entertaining.

So at a friend’s party last night, I found this book on Graph Theory. I just asked my hosts whose book it was, got the answer and put it back.

As many of you know, whenever we host a party, we use graph theory to prepare the guest list. My learning from last night’s party, though, is that you should not only use graph theory to decide WHO to invite, but also to adjust the times you tell people so that the party has the best outcome possible for most people.

With the full benefit of hindsight, the social network at last night’s party looked approximately like this. Rather, this is my interpretation of the social network based on my knowledge of people’s affiliation networks.

This is approximate, and I’ve collapsed each family to one dot. Basically it was one very large clique, and two or three other families (I told you this was approximate) who were largely only known to the hosts. We were one of the families that were not part of the large clique.

This was not the first such party I was attending, btw. I remember this other party from 2018 or so which was almost identical in terms of the social network – one very large clique, and then a handful of families only known to the hosts. In fact, as it happens, the large clique from the 2018 party and from yesterday’s party were from the same affiliation network, but that is only a coincidence.

Thinking about it, we ended up rather enjoying ourselves at last night’s party. I remember getting comfortable fairly quickly, and that mood carrying on through the evening. Conversations were mostly fun, and I found myself connecting adequately with most other guests. There was no need to get drunk. As we drove back peacefully in the night, my wife and daughter echoed my sentiments about the party – they had enjoyed themselves as well.

This was in marked contrast with the 2018 party with the largely similar social network structure (and dominant affiliation network). There we had found ourselves rather disconnected, unable to make conversation with anyone. Again, all three of us had felt similarly. So what was different yesterday compared to the 2018 party?

I think it had to do with the order of arrival. Yesterday, we were the second family to arrive at the party, and from a strict affiliation group perspective, the family that had preceded us at the party wasn’t part of the large clique affiliation network (though they knew most of the clique from beforehand). In that sense, we started the party on an equal footing – us, the hosts and this other family, with no subgroup dominating.

The conversation had already started flowing among the adults (the kids were in a separate room) when the next set of guests (some of them from the large clique arrived), and the assimilation was seamless. Soon everyone else arrived as well.

The point I’m trying to make here is that because the non-large-clique guests had arrived first, they had had a chance to settle into the party before the clique came in. This meant that they (non-clique) had had a chance to settle down without letting the party get too cliquey. That worked out brilliantly.

In contrast, in the 2018 party, we had ended up going rather late which meant that the clique was already in action, and a lot of the conversation had been clique-specific. This meant that we had struggled to fit in and never really settled, and just went through the motions and returned.

I’m reminded of another party WE had hosted back in 2012, where there was a large clique and a small clique. The small clique had arrived first, and by the theory in this post, should have assimilated well into the party. However, as the large clique came in, the small clique had sort of ended up withdrawing into itself, and I remember having had to make an effort to balance the conversation between all guests, and it not being particularly stress-free for me.

The difference there was that there were TWO cliques with me as cut-vertex.  Yesterday, if you took out the hosts (cut-vertex), you would largely have one large clique and a few isolated nodes. And the isolated nodes coming in first meant they assimilated both with one another and with the party overall, and the party went well!

And now that I’ve figured out this principle, I might break my head further at the next party I host – in terms of what time I tell to different guests!

Cliquebusting

Last evening we hosted a party at home. Like all parties we host, we used Graph Theory to plan this one. This time, however, we used graph theory in a very different way to how we normally use it – our intent was to avoid large cliques. And, looking back, I think it worked.

First, some back story. For some 3-4 months now we’ve been planning to have a party at home. There has been no real occasion accompanying it – we’ve just wanted to have a party for the heck of it, and to meet a few people.

The moment we started planning, my wife declared “you are the relatively more extrovert among the two of us, so organising this is your responsibility”. I duly put NED. She even wrote a newsletter about it.

The gamechanger was this podcast episode I listened to last month.

The episode, like a lot of podcast episodes, is related to this book that the guest has written. Something went off in my head as I listened to this episode on my way to work one day.

The biggest “bingo” moment was that this was going to be a strictly 2-hour party (well, we did 2.5 hours last night). In other words, “limited liability”!!

One of my biggest issues about having parties at my house is that sometimes guests tend to linger on, and there is no “defined end time”. For someone with limited social skills, this can be far more important than you think.

The next bingo was that this would be a “cocktail” party (meaning, no main course food). Again that massively brought down the cost of hosting – no planning menus, no messy food that would make the floor dirty, no hassles of cleaning up, and (most importantly) you could stick to your 2 / 2.5 hour limit without any “blockers”.

Listen to the whole episode. There are other tips and tricks, some of which I had internalised ahead of yesterday’s party. And then came the matter of the guest list.

I’ve always used graph theory (coincidentally my favourite subject from my undergrad) while planning parties. Typical use cases have been to ensure that the graph is connected (everyone knows at least one other person) and that there are no “cut vertices” (you don’t want the graph to get disconnected if one person doesn’t turn up).

This time we used it in another way – we wanted the graph to be connected but not too connected! The idea was that if there are small groups of guests who know each other too well, then they will spend the entirety of the party hanging out with each other, and not add value to the rest of the group.

Related to this was the fact that we had pre-decided that this party is not going to be a one-off, and we will host regularly. This made it easier to leave out people – we could always invite them the next time. Again, it is important that the party was “occasion-less” – if it is a birthday party or graduation party or wedding party or some such, people might feel offended that you left them out. Here, because we know we are going to do this regularly, we know “everyone’s number will come sometime”.

I remember the day we make the guest list. “If we invite X and Y, we cannot invite Z since she knows both X and Y too well”. “OK let’s leave out Z then”. “Take this guy’s name off the list, else there will be too many people from this hostel”. “I’ve met these two together several times, so we can call exactly one of them”. And so on.

With the benefit of hindsight, it went well. Everyone who said they will turn up turned up. There were fourteen adults (including us), which meant that there were at least three groups of conversation at any point in time – the “anti two pizza rule” I’ve written about. So a lot of people spoke to a lot of other people, and it was easy to move across groups.

I had promised to serve wine and kODbaLe, and kept it – kODbaLe is a fantastic party food in that it is large enough that you don’t eat too many in the course of an evening, and it doesn’t mess up your fingers. So no need of plates, and very little use of tissues. The wine was served in paper cups.

I wasn’t very good at keeping up timelines – maybe I drank too much wine. The party was supposed to end at 7:30, but it was 7:45 when I banged a spoon on a plate to get everyone’s attention and inform them that the party was over. In another ten minutes, everyone had left.

Mixing groups at parties

I normally don’t like mixing groups at parties I host – that sometimes leaves me as a “cut vertex” meaning that I have to personally take it upon myself to entertain one or more guests and can’t leave them to be “self-sufficient”. You might recall that a bit over two years ago, I had tried to use social network analysis to decide who to call for my birthday party.

However, for unavoidable reasons, we had to call a mixed set of friends to a party yesterday. We’re “putting BRexit” later this week (moving back to Bangalore), and considering that there were so many people we wanted to meet and say goodbye to, we decided that the best way of doing so was to call them all together to one place.

And so we ended up with a bit of a mixed crowd. The social network at yesterday’s party looked like this. For the sake of convenience, I’ve collapsed all the “guest families” into one point each. The idea is that while a guest family can “hang out among themselves”, they needn’t have come to the party to do that, and so it fell upon us hosts to talk to them. 

So the question is – with three hosts, one of whom was rather little, how should we have dealt with this assortment of guests?

Note that pretty much everyone who RSVPd in the affirmative came to the party, so the graph is unlikely to have been more connected than this – remove my family and you would have a few islands, including a couple of singletons.

Should we have spent more time with the families that would’ve been singletons than with those who knew other guests to interact with? Or was it only fair that we spent an equal amount of time with all guests? And considering that we could deal with guests on the right side of the graph “in twos”, did that mean we should have proportionately spent more time with those guys?

In any case, we took the easy way out. Little Berry had an easy time since there were two entities she knew, and she spent all her time (apart from when she wanted parental attention) with them. The wife and I were taking turns to buy drinks for freshly arrived guests whenever they arrived, and on each occasion we helped ourselves to a drink each. So we didn’t have to worry about things like social network dynamics when we had more important things to do such as saying goodbye.

I just hope that our guests yesterday had a good time.

Oh, and way too many conversations in the last two weeks have ended with “I don’t know when I’ll see you next”. It wasn’t like this when we were moving the other way.

 

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.