>Unfortunately, the results showed a true-negative rate of 78%. i.e. most of the time the model failed to predict when a meaningful conversation was about to occur.
>...
>The model is significantly worse than a coin-flip. Obviously, this is not good; and given that the majority of conversations on the site are trivial
1. This isn't correct use of the term "true negative". A true negative is when your model predicts a negative, and the label is actually negative. "the model failed to predict when a meaningful conversation was about to occur" would correspond to a false negative (the model predicts negative, the the label is actually positive)
2. "The model is significantly worse than a coin-flip" - Talking about coin flips hardly makes sense if the majority of conversations on the site are trivial.
A better way to think about this question would be from a Bayesian perspective. Define a random variable L for linkage. L=True if there exists a user B such users A and C both had non-trivial conversations with B. L=False otherwise. Then define a random variable T for whether the conversation is trivial or not. Then you can compute P(T=False|L=True) and P(T=False|L=False) from your data.
It could be that what this article is trying to say is that P(T=False|L=False) > P(T=False|L=True), i.e. the presence of a linkage decreases the probability of a nontrivial conversation.
This could occur if, for example, most users of Chatroulette are using it as a dating site, and since heterosexual people outnumber gay people, most nontrivial conversations occur between men and women. So if there's a linkage between A and C, that predicts that A and C are of the same gender, and they won't be interested in talking to each other.
Anyway, I didn't read any further than that, but I would suggest just ranking users based on their propensity for nontrivial conversations and connecting users with other users who like to have nontrivial conversations (or perhaps even better, compute the mean/median conversation length for each user to get a sense of their preferred conversation length, then connect users to other users who have a similar preferred conversation length).
I suspect there's room to use machine learning to improve Chatroulette a lot, even to the point where it could be the next Facebook. People already pay thousands of dollars to attend Harvard etc. for the networking. You just have to use machine learning tools correctly and find a way to capture some of that value.