3
$\begingroup$

Recently, I started to think of a problem involving the use of Twitter data that would involve finding pairs of users that participate in the most conversations. For example, with each tweet, you get the root conversation id along with a user id for that specific tweet. What I want to do is find pairs of users that participate in the same threads and also find the pair of users that have participated in the most threads (participation in a thread means that in one tweet, you would see a user id associated with the same conversation id as another user id.

This would involve first scanning every tweet (N) to fetch conversation, user id pairs. After doing this, I would have a list of user ids for each conversation id. I would then scan every user id association with each conversation id and then proceed to the next conversation id, scan each user id and compare against the previous list associated with previous conversation ids.

At the very least, I feel like the best method to do this would be, at a minimum, nlogn, but the method I'm proposing seems like it would make more comparisons than nlogn, but not as many as n^2.

How would I go about computing big O in this scenario?

Edit: I don't know if it is good form to edit one's question with a possible solution, but it appears you would need to scan each conversation (K) to get a list of tuples that associate users for that conversation (N^2-N)/2. You can then hash the tuple and increment the value of that dict key by one each time you discover the same tuple in another conversation. So ultimately you have to do (N^2-N) comparisons times K (each conversation). So the Big O would be larger than nlogn but not N^2. If I remember correctly, you drop the constants for big O so the running time would be somewhere around N^2-N * K (for each conversation). I'm not sure how to correctly form the big O here (what do you do with K?).

$\endgroup$
2
  • $\begingroup$ I don't understand what you mean by "scan every user id association with each conversation id and then proceed..." $\endgroup$
    – D.W.
    Jun 15 at 20:23
  • $\begingroup$ Sorry if I worded that poorly. As a more simplistic example, let's pretend we are only analyzing two conversations. I will have a set of tweets for both conversations. Each tweet has the root tweet id (which can serve as the conversation id) and each tweet will have one user id. My first step would be collecting all user ids for each unique conversation id. What I am left with is two sets -- each with a unique conversation id. I would need to iterate over the user ids for each set and find overlaps where two users participated in two different conersations. I hope that example is clearer. $\endgroup$ Jun 15 at 23:18
2
$\begingroup$

It might be nice to model the problem as a bipartite graph $(U, C, E)$ where $U$ is the set of users, $C$ is the set of conversations, and $E \subseteq U \times C$ are edges for participation.

In this setting, for each user, the set of other users that participate in the same conversations are its neighbors-of-neighbors. Let's make a new graph where each user is connected to its neighbors-of-neighbors. In the new graph, give each edge a weight which is the number of unique conversations in which those two users participate. This can all be computed in O(|E|) because each edge in the new graph corresponds to two edges of the original.

In the new graph, look at the edge with the largest weight. The endpoints are the pair of users that converse the most with each other.

(I think this is approximately the algorithm that you had in mind. Using a bipartite graph makes things clearer.)

All together, that gives you O(|E|) for computing the result. I don't think there's any other algorithm that can do better than $O(|E|)$ in the worst case.

EDIT: this is too slow, because the new graph can be huge, much larger than |E|. See comments.

$\endgroup$
5
  • 2
    $\begingroup$ This doesn't look correct to me. I think the size of your new graph can be quadratic in the size of the original graph. For instance, a conversation with 100 users in it will lead to a graph with 4950 edges. So, I don't think you can compute it all in $O(|E|)$ time. The justification "each edge in the new graph corresponds to two edges in the original" does not imply $O(|E|)$ running time. $\endgroup$
    – D.W.
    Jun 15 at 19:11
  • $\begingroup$ Ah good catch. For large conversations the new graph is much too large. I edited the answer. $\endgroup$ Jun 15 at 19:51
  • $\begingroup$ Thank you! This is a step in the right direction. Ultimately, I'm sure this problem can be reduced to a more well known problem. Within each conversation, we really only care about unique user ids associated with each unique conversation. However, this problem becomes computationally expensive given the technique I would use to approach it. The problem could probably be further optimized by dropping all user ids that only appear once from all conversations as they would never match two convos with another user. We will still be left with N conversations with M unique users in each. $\endgroup$ Jun 16 at 0:05
  • $\begingroup$ It's quite confusing to come to an answer for the first time that contains strikethrough text and a bolded edit tags. Please see here on Meta for a related question. Also, we can't understand your answer once the comments are cleaned up :S Could you do an edit based on this? $\endgroup$
    – Juho
    Jun 16 at 5:33
  • $\begingroup$ @SamWestrick -- Your answer appears to be almost there. If you want to take the time to clean it up a bit and put the big O solution towards the end, I'd be happy to accept your answer. Great work! $\endgroup$ Jun 16 at 17:53
2
$\begingroup$

It's a bit pedantic, but problems and functions don't have big-O representations, algorithms do. There are many algorithms that could implement the function you describe, and they have different big-O performance. It's confusing, because generally people want the fastest algorithm for a given problem, so you'll hear things like "sorting is n*log(n)", which is not formally true.

The second thing to think about for your problem is "What does N represent?"

In a problem where there are several "sizes", it's perfectly reasonable to use different letters to represent different things. So let's say that there are N conversations and the longest one is M posts long.

An algorithm to generate your answer (ignoring a lot of details) could look something like:

# maps every pair to the number of conversations they've shared. e.g. "alice$bob" -> 10
pair_frequency = dict()
for convo in conversations:
  for tweet in convo:
    for other_tweet in convo:
      pair_frequency[tweet.userid + "$" + other_tweet.userid] += 1

# which pair is most frequent?
max = 0
max_pair = null
for pair, freq in pair_frequency:
  if freq > max:
    max = freq
    max_pair = pair
return max_pair

This algorithm is O(N * M^2), since, for each tweet in each conversation, it iterates over every other tweet in the conversation.

This might or might not be a good algorithm for you to actually use, but it's how I would start thinking about the problem in terms of big-O.

Something to think about - in reality, it's probably important to know the average number of tweets in a conversation, but for big-O analysis I chose M to be the length of the longest thread.

$\endgroup$
1
  • $\begingroup$ "It's a bit pedantic, but problems and functions don't have big-O representations, algorithms do." -- It might be pedantic, but it is a very important point and I appreciate you correcting me there. That's an important distinction. $\endgroup$ Jun 20 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.