Clique Counting
Cliques in computer science…and socially
ALOR SAHOO - THE TECH
ALOR SAHOO - THE TECH
ALOR SAHOO - THE TECH
ALOR SAHOO - THE TECH
ALOR SAHOO - THE TECH
ALOR SAHOO - THE TECH
ALOR SAHOO - THE TECH
ALOR SAHOO - THE TECH
ALOR SAHOO - THE TECH
This article was originally published on Aug. 3, 2023 under Issue No. 11.
I’ve been frustrated by the idea of cliques: both in computer science and socially.
Let me explain. The computer science “clique maximization” problem kinda goes like this: Within a graph (made up by vertices and edges), find and list all the biggest cliques, where a clique is a group of vertices where everyone is connected to everyone else.
First, let’s define some terms. This is a graph, with smiley-face nodes and edges between them. Note that every intersection of edges is not necessarily a node:
(see Photo A)
Here’s an example of a graph, with the biggest clique colored in red:
(see Photo B)
How easy of a problem is it to solve? Very roughly, it’s considered a “hard” problem to solve computationally. That’s kind of funny to me, given how “cliques” also used to describe exclusive social groups.
To integrate these two different views on cliques, here's a little walkthrough. Imagine that everyone in the MIT community is represented by a node:
(see Photo C)
There’s an edge between two nodes if and only if they are acquainted with each other.
(see Photo D)
Clearly, not every relationship is equally strong. So let’s assign some arbitrary weights to represent the “value” of a relationship. Yes, this is very reductive:
(see Photo E)
Hold on again, though. In some relationships, there's some unevenness, with one person putting in more energy than the other. For another oversimplification, let’s direct our edges, so that we can now have up to 2 weighted edges between any 2 nodes. Here’s an example where the left person feels they have a stronger relationship with the right than the other way around:
(see Photo F)
Of course, there are even more complications. For example, each person/node can only expand certain amounts of energy socially. Graphically, this limits the number of weights “exiting” a specific node, unless a node stresses itself out:
(see Photo G)
My eventual conclusion is the following: people can’t be friends with everyone they might possibly want to be friends with, unless they neglect some other aspect of their life.
When I first spawned onto the MIT social graph during CPW, I looked for people nearby — people with similar experiences, interests, vibes, etc. At first, I was confused: the connections I’d formed seemed both sparse and weak. At CPW, there were obviously some people that I knew, and that knew of me, through Instagram or Messenger — but that was mostly it. As I walked through and across and over all the subgraphs of MIT, I felt disconnected:
(see Photo H)
This disconnect was surprisingly OK for me, as long as it was temporary. Surely, I just needed to wander through some more vertices, cross some edges, and then I’d stumble into the right group of people.
In other words, I wanted to solve my personal MIT clique maximization problem — and fast.
This epiphany hit me in the middle of CPW. Boba started taking its toll on my tastebuds, so I went to grab a real lunch at a dining hall. Nearby some dozen or so prefrosh were hanging out. I grabbed my food, sat at a nearby table, and while wolfing down rice pilaf, I caught casual bits of conversation — a “Mrs. So-and-So” and a “remember when XYZ did ABC?” and so on. Then it hit me:
Duh, they all went to the same high school.
It stung knowing that I’d never get that big, nostalgic high school-MIT crossover. Even when I met people I’d already known, I felt like I was missing out. Someone else always seemed to either be a part of cooler graphs or more graphs — sometimes both.
By Fall 2022, I started to realize that optimizing my number of connections wasn’t a healthy goal. The primary driving force was exhaustion: I was too tired to “keep up.” It worked out: I resonated with my floor in BC, which is small, but closely-linked. I felt good, so cliques and social groups were out of mind.
However, later on, I started thinking about a new aspect of the “clique maximization” problem: what even defines one? Does a wing of a dorm with harmless-ish inside jokes qualify? When do group events go from special and inclusive to irritating and exclusive? Can a club that hangs out outside meetings all the time become a clique? Was I part of one without realizing?
For sure, some of these groups are bound to be tight-knit: living groups, certain clubs, pset groups for grueling classes, and so on. But a lot of them are much bigger, once you include MEng students, alumni, friends of friends, etc.
But what was the biggest one? Hard to define, but an obvious guess is each graduating class, if that counts. Between sophomore ring delivery to annual formals to fancy senior spring events, they’re pretty cohesive, as much as a group of more than a thousand students can be.
So, as a quick exercise, I decided to calculate my “MIT friend age” average. Here’s how it works: define 0 to be a brand-new frosh, 4 to be a graduated senior, and everyone else in between. For example, in December 2022, my age was 0.4, since I was roughly done with a semester.
My average? 2.3. Was that a bad thing? I didn’t know. Was I just not “froshy” enough? I was pretty worried, and for a few weeks, I repeatedly asked myself:
(see Photo I)
Now, a semester later, I don’t have the answers.
But I also don’t care.
Because all approaches quantifying any aspect of this problem boil down to the same ideas: First of all, that being closer with some people means being more distant with others. Second of all, there is no perfect way of reconciling this difference whenever two corners of the MIT social graph intersect.
As a result, I’m giving up on the MIT clique maximization problem. I’ve spent way too long adding edges to my node, adjusting the weights, and removing edges, and so on. I’m going to just let my edges naturally form, break, weaken, and strengthen as the years go by.
Most importantly, I learned that tinkering with my graph and trying to “solve” this unproblematic problem is futile: even the computer scientists admit that.