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!

Evaluating WhatsApp groups

Over time I’ve come to become a member of several WhatsApp groups. Some of them are temporary, designed to simply coordinate on a particular one-off event. Others are more permanent, existing over a long term, but with no particular agenda.

Over this time I’ve also exited several WhatsApp groups, especially those that have gotten a bit annoying. I remember this day last year when I stepped in and out of a meeting, and I found a hundred messages on a family WhatsApp group, most of them being random forwards, and a few of them being over a page long. I quickly exited that group.

Not everyone quickly exits groups they don’t like, though. There is social pressure to remain, since anyone’s exit gets publicly broadcast in the group. Being a member of a WhatsApp group is the latest measure of conformity, and irrespective of how annoying some groups are, one is forced to endure.

Not all WhatsApp groups are annoying, though. Some groups I’m a member of are an absolute joy. There are times when I explicitly choose to initiate a conversation within the group, than bilaterally, so that others in the group can pitch in. And this taking of the conversation to the group is usually not minded by the intended counterparty as well.

Thinking about good and bad WhatsApp groups, I was wondering if there is a good and clean metric to determine how “good” or “useful” a WhatsApp group might be. Based on my experience, I have one idea. Do let me know if you know a better way to characterise whether a WhatsApp group is going to be good or bad.

When you have a WhatsApp group with N people, you are essentially bringing together N * (N-1)/2 pairs of people. Now, some of these pairs might get along fantastically well. Other pairs might loath each other. And yet others are indifferent to each other.

My hypothesis is that the more the number of pairs in a group that like to talk to each other, the better the group functions (yes it’s a rather simple metric).

Now, this hypothesis is rather simplistic – for example, you can have threesomes of people whose mutual relationship is very different from that of any pair taken together. So this ignores a higher order correlation term, but improves simplicity. It’s like that benzene ring, where six carbon atoms bond together in a way no two of them as a pair can (forget the scientific term for such bonding)!

Yet, what we have here is a good measure of cohesion within the group. It also explains why sometimes the addition of a single member can lead to the destruction of the group – for it can increase the proportion of people who don’t like to talk to each other!

The model is incomplete, though. For now, it doesn’t differentiate between “don’t care conditions” (people in the group who are indifferent to each other) and “don’t get alongs”. If we can incorporate that without making the formula more complex, I think we might be up to something.

Maybe we should form a WhatsApp group to discuss what a good formula might look like!

InMails and the LinkedIn backfire

A few months back I cleaned up my connections list on LinkedIn. Basically I removed people who I don’t “know”. I defined “know” as knowing someone well enough to connect them to someone else on my network (the trigger for a cleanup was when someone asked me to connect them to someone else on my network who I hardly knew).

The interesting thing about the cleanup was that a lot of the spurious connections I had on LinkedIn were headhunters. Thinking back at how they got in touch with me, in most cases it was with respect to a specific opportunity for which they were finding candidates. Once the specific opportunity had been discussed there was no value of us being connected on LinkedIn, and were effectively deadweight on each other’s networks.

Over the last couple of days, ever since I wrote this piece for Mint on valuation of startup ratchets, I’ve got several connection requests, all from people I don’t know. Normally I wouldn’t accept these invitations, but what is different is that most requests have come with non-standard messages attached. Most have mentioned that they liked my Mint piece and so want to either connect or discuss it.

When you want to simply exchange messages with someone, there is no need to really add them as a “friend”. Except that LinkedIn’s pricing policy makes this kind of behaviour rational.

LinkedIn offers a small number of “InMails” which you can send to people who you aren’t directly connected to. Beyond this number, each InMail costs you money. So if you want to have a discussion with someone you’re not connected with, there’s an element on friction.

There’s a loophole, however. You can send messages for free as long as they go along with a connection request. And if that request is accepted, then you can have a “free” conversation with that person.

So given the current price structure, if you want to have a conversation with someone, you simply send your initial message as part of a friend request. If the person wants to continue the conversation, the request will get accepted. If not you haven’t lost anything!

Then again, there are mitigating features – an InMail won’t get charged unless there is a reply, and LinkedIn’s UI is so bad that it takes effort to read messages attached to connection requests. So this method is not foolproof.

Still, it appears that LinkedIn’s pricing practice (of charging for InMails) is destroying the quality of the network by including spurious links. I guess they’ve done a cost-benefit analysis and believe that the cost of spurious connections is far lower than the revenue they make from InMails!

 

Social Reading

Feedly, the RSS Reader I’ve been using ever since Google Reader shut down, has announced a feature called “Shared Collections“. This is something like the Google Reader shared items (much loved by its loyal users including me, but something that apparently wasn’t good enough for Google to retain), except that it is available only for premium users.

 

While this is in theory a great move by Feedly to start shared collections, recognising the unfulfilled demand for social reading post Google Reader, their implementation leaves a lot to be desired. And I’m writing this without having used the feature, for, in an extremely daft move, it is available only for pro users. My problem is with the pricing model, which charges content creators (or curators or aggregators, if you like to call them that) for sharing content!

There are so many things wrong with this that I don’t know where to start. Firstly, if you charge people for creating content, that significantly increases the barrier to creating content. If there is an article I like and want to share with my (currently non-existent) followers, the fact that I have to create a premium account to do so means that the barrier to doing so is too high.

Secondly, if I’m going to be a consumer of shared collections from other people, I’ll need a certain critical mass of friends before I start using the feature. I won’t start using a feature only because one or two friends are curating content on it. The critical mass is much higher. And by putting barriers to entry to people who want to share, it makes this critical mass even more difficult to obtain.

Thirdly, Feedly doesn’t have a social network of itself so far (though I’m not aware what permissions they’ve taken from my when I used my Google account to log in to the service). And without having a ready social network for discovery (Google Reader leveraged the Google Talk network), how do they expect people to discover each other’s collections, once created? Are they relying on external networks such as Facebook or Twitter?

It is not easy to build a social network of curation. Google Reader had managed it quite well back in the day by first allowing people to share items without comment, then add external content, and then to add comments. It was an extremely powerful way for people to share blogs and other content, and discussion on that was rather active. I even remember quite a few people adding me on Google Talk for the sole reason of wanting to follow my Shared Items.

In recent times we’ve seen the news aggregator app Flipboard starting its personal collections feature. I have a collection, but don’t remember the last time I put something into it – for without any interaction on that, there’s absolutely no motivation. Flipboard, by the way, has access to your Facebook and Twitter graphs, and so has access to some sort of a social network. Yet, despite keeping the feature free, they haven’t been able to generate sufficient activity on it.

Feedly has got just about everything wrong with its Shared Collections feature. There is disincentive for content creators. There is no incentive for content consumers. They don’t have a ready social network. And there doesn’t seem to be any interaction.

If only Google were to bring back Google Reader and Shared Items, now that they’ve decided to dismantle Google+.

 

On apps tracking you and turning you into “lab rats”

Tech2, a division of FirstPost, reports that “Facebook could be tracking all rainbow profile pictures“. In what I think is a nonsensical first paragraph, the report says:

Facebook’s News Feed experiment received a huge blow from its social media networkers. With the new rainbow coloured profile picture that celebrates equality of marriage turned us into ‘lab rats’ again? Facebook is probably tracking all those who are using its new tool to change the profile picture, believes The Atlantic.

I’m surprised things like this still makes news. It is a feature (not a bug) of any good organisation that it learns from its user interactions and user behaviour, and hence tracking how users respond to certain kinds of news or updates is a fundamental part of how Facebook should behave.

And Facebook is a company that constantly improves and updates the algorithm it uses in order to decide what updates to show whom. And to do that, it needs to maintain data on who liked what, commented on what, and turned off what kind of updates. Collecting and maintaining and analysing such data is a fundamental, and critical, part of Facebook’s operations, and expecting them not to do so is downright silly (and it would be a downright silly act on part of the management if they stop experimenting or collecting data).

Whenever you sign on to an app or a service, you need to take it as a given that the app is collecting data and information from you. And that if you are not comfortable with this kind of data capture, you are better off not using the app. Of course, network effects mean that it is not that easy to live like you did in “the world until yesterday”.

This seems like yet another case of Radically Networked Outrage by outragers not having enough things to outrage about.

Twitter and Radically Networked Outrage

The concept of Radically Networked Outrage was originally conceived by my Takshashila colleague Pavan Srinath. Having conceived of it, he had promised to blog about it, but it’s been over a month and he’s yet to get down to it. Given this delay, I think I’m justified in stealing this blogpost.

One of the pet themes professed by people at Takshashila, especially Nitin Pai, is the concept of “radically networked societies”. There are too many posts to link to, so I’ll just link to this book chapter that Nitin has written, and to this TEDx talk:

So the whole concept is that societies nowadays are not hierarchical like in the past, but “radically networked”, in that the density of the graph of people in the world has increased significantly with technology. Not only has the density gone up – which means that people are connected to significantly more people than in the past – but technology has enabled people to communicate rapidly.

So you have twitter where you can broadcast your short thoughts. WhatsApp groups enable you to send, and propagate, messages to multiple people at once. This, combined with increased graph density, has resulted in ability for large numbers of people to coordinate and organise, and presents new kinds of governance challenges. For example, it was radically networked societies that resulted in the so-called Arab Spring (which, in hindsight, has mostly led to chaos). Radically networked societies also resulted in the Anna Hazare movement in 2011, which in turn led to the formation of the Aam Aadmi Party, which has taken Delhi by storm.

When societies are so radically networked that they can cause revolutions which can result in the overthrow of governments, they can also such radical networking for lesser causes, such as outraging. When the odd thatha outrages about a certain happening or piece of news, it doesn’t have any impact, and ends up in at best a letter to the editor, and dies a quiet death. If a handful of unconnected thathas outrage about something, it will still not amount to much, and one of their letters to the editor will get published.

However, put together a large number of people densely connected to each other, any outrage in such network will be immediately seen and noticed, and has the potential to go viral. The thing about outrage is positive feedback – when you see someone outraging about a particular topic that you mildly outrage about, you feel encouraged to make your mild outrage public. As the number of people in your network outraging about something increases, the likelihood of you joining in the outrage increases.

So as you can imagine, once there a certain critical mass to outrage about a particular issue, it can go truly viral, until just about everyone is outraging about the topic.

And outrage can have inter-issue positive feedback also. Once you are used to seeing a certain amount of outrage on your twitter timeline, you feel encouraged to make public any marginal outrage about any other issue also. And a number of people getting marginally thus pushed to make their outrage public can result in a further increase in radically network outrage!

We live in a time when societies are radically networked, and outrage is the order of the day. And since outrage causes more outrage, this outrage is unlikely to reduce. It is impossible to say anything remotely controversial on social media nowadays – a pack of outragers will immediately hound you. There are already some victims of such radically networked outrage – like the PR professional Justine Sacco who lost her job after an outraged mob failed to see the humour in her tweet, or scientist James Watson who had to auction his Nobel Prize after outrage about his comments about race had led to speaking assignments dying out, or footballer Ched Evans who is unable to find a club to hire him after doing time for rape. The latest victim of radically networked outrage is Nobel laureate Tim Hunt, who resigned his position as Professor following radically networked outrage about certain remarks he made that were deemed sexist.

And there is no escaping such outrage. In an attempt to escape it, I pruned my Twitter following list a couple of days back, unfollowing people who are highly prone to participate in radically networked outrage. At the end of it, my following list had grown so thin that there was no value for me in Twitter any more. I would just check twitter in the hope of interesting tweets, but come across hardly any tweets.

So today I begin my third sabbatical from Twitter. The first one (January 2014) lasted a month, and the second (August to November 2014) lasted three. I don’t know how long this will last. I’ll be robbed of interesting discussions for sure, but can do without all the negativity prevalent all over my timeline. But I’m sure Radically Networked Outrage will have its way of getting to me again!

In October, during my last sabbatical, I had written about the same topic. And in December, I had written about the “mob courts” of social media.

Value addition through comments

My friend Joy Bhattacharjya is a star on Facebook. He has a large number of friends (I haven’t bothered to see how many), most of whom seem to have him on their “good friends” list thanks to which they get each and every one of his updates (I had recently cribbed about Facebook’s algorithm, but when your friends love you, it doesn’t matter). And most of his updates are extremely insightful, some of them funny. If you are his friend, it is not hard to guess why his updates are so popular.

There is only one problem – it is impossible to comment on them. I mean, the comments section is always open, but the problem is that by the time you see an update, so many people would have commented on them that adding one more comment there doesn’t add any value. Writing something there, it seems, is not worth the time, for you assume that given the sea of comments the author won’t have time to read and appreciate your wisecrack. And so you move on.

Recently one friend announced his engagement. Another announced the birth of her child. It was again impossible to add value via comments to either – there had already been so many comments that adding one more wouldn’t add any value! I doubt if these “announcers” even bothered to read through all the comments people had posted. A compression algorithm might have done the trick for them, for most of them were extremely banal and non-value-adding “congrats” posts!

The last time my birthday was listed on Facebook (2010, if I’m not wrong), I got so many scraps on my wall that I had no time to read them, let alone respond to them. I promptly delisted my birthday from Facebook, with the result that nowadays hardly anyone wishes me on my birthday. Not on Facebook, at least, and I’m happy about not having to respond to a mechanical action!

On a similar note, one thing I get very pissed off (on Facebook) is “thread hijacking”. You get a nice discussion going in the comments thread on some post, and then someone else comes in (usually an aunty) and says something so banal that you don’t want to be seen on that thread any more, and the discussion goes for a toss. Oh, and such thread hijacking is more prevalent on Facebook’s other product Whatsapp (:P ), especially on groups where lack of threaded conversation means deep discussions are highly prone to being disrupted by long forwards someone sends!

Recently, Facebook introduced the threaded comments feature, one that I loved so much that I resisted a move away from Livejournal for ages just for that one feature, and when I moved to this blog, one of the first plugins I installed was one that allowed for threaded comments. Facebook has done badly, though. I use it primarily through the iPad app, and the threaded comments suck big time, requiring way too many clicks to navigate. If done so badly, I’d prefer blogspot-type dumb linear comment scheme only!

I sometimes wonder why I’m on Facebook at all. I used to use it at one point in time to look at people’s photos, and what they were up to. But now i find that it’s impossible to subscribe to a person’s photos without subscribing to her political views also, which are generally downright uninformed and sometimes extreme. And thanks to blogger-style comments, you cannot keep uninformed people out of your discussion on Facebook, unlike Twitter – they just keep popping up.

And there is no way for me to explicitly tell Facebook I want to see more or less of someone’s feed (like I could with Pandora, back when I used it). I have to rely on the algorithm.

All in all, Facebook seems like a dumb social network. To use a concept I’d mentioned here a few months back, it’s an “events and people” social network, with Twitter being more conducive to ideas. I sometimes end up asking myself why I’m on Facebook at all. And then I realise that there is no other way for me to access Joy’s updates!