# How to find similar users in a social network

I have a set of users from a social network. These users are represented by large sparse vectors. Let's say that a small subset of those users bought a ticket for a particular movie. How could I find a subset of other users from the same network that could be interested in the same event? Thus, for example I could show them an add with that event.

EDIT: More details:

First of all the example may not be best I could have chosen. The users are returning clients of a company (i.e. they usually buy tickets for racing shows). Let's say there are thousands of them (~10k). So the company knows who they are. Each of those users is represented by long unary vector that is highly sparse (~60k dimensions). The vector represents what those users like (hence unary) (It is safe to say that this is static information). The task is to identify about 100k other users from the same social network, so that they could be recommended similar events. The entire network consists of about 100M users. So, the solution is also constrained by the computation time.

@Peter I decided to mention that the problem concerns a social network, because there are some underlying problems like outliers. So, for example encoding of the vectors may be recommended.

• Maybe search for clustering in social networks?. Aug 21, 2019 at 10:27
• @kjetilbhalvorsen If you know any clustering method that you could force to cluster on selected group of users, that would be great. Aug 21, 2019 at 10:46
• Where is the social network aspect of this? Aug 21, 2019 at 11:59
• @Peter Flom: It was tagged as social-network, and it is in the first sentence ... But clustering might be more than is asked for, since a subset of other users from the same network that could be interested in the same event? might be asking just for one cluster containing a small set of members, not clustering everybody. Aug 21, 2019 at 12:21
• @kjetilbhalvorsen Yeah, I saw the tag and the first sentence; I guess I wasn't clear enough. I'm asking why the social network part is relevant. Aug 21, 2019 at 12:23

This is a typical classification problem. I will explain how I would solve in a simplified way, PROVIDED THAT there is a temporal problem in classifying people that have already bought a ticket against people that have not yet bough a ticket (I.e you do not fully know whether such people have not bought but they will buy, or they haven’t bought and they will never buy). We will come back on this issue at the end of the answer. Anyway take this approach as a simplified and non-exhaustive example.

Firstly assume the whole dataset of the social network has N members, where m have actually bought the tickets, and N-m=k haven’t. Ignore the problem that some of them may do so in the near future before the event for now.

First you wish to collect more data about the users that in your opinion are suitable for a choice of buying the ticket (data that may be numerical or categorical about their spending capacity, proximity to the event, musical tastes, ... the more the better: I will leave this problem to your creativity; clearly the more the data collected are logically correlated to the purchase of a ticket the better it is, but also other data that are APPARENTLY not relevant may be relevant in the end, so just collect as many data as you can.. this is why data are so valuable nowadays!)

Then after doing this, you end up with a set of f features for all the N users. Now assume to split the k users not having bough yet in two groups of equal size. I am just saying equal size for convenience of explanation, maybe it is not even optimal. Suppose it is. Group 1, made of half of the individuals not having bought, is merged into the training dataset along with the m subjects. Group 2 is left outside.

Now your training sample is made of m+k/2 individuals. Now split it again and leave out a portion, suppose a 25% for a pure exemplification. This will be our validation dataset. Now define as training group the other (m+k/2)*75% subjects. And via machine learning (even via simple multivariate logistic regression here if the fit is good enough) you can solve a classification problem on the (m+k/2)*75% subject where the dependent variable is 1 if they bought a ticket and 0 if they didn’t. You will find the most important among the f features for each subject in predicting the choice and estimate an equation giving a score representing the probability that each subject buys a ticket based on his/her own features.

Now you can see what the predicting capability and classification power of the model is, by validating your model in the validation dataset of (m+k/2)*25% individuals. And compare different model hypotheses on that validation to see which of the model is better at classifying the subjects out of the initial training sample. Then you choose the model specification that does better (again, I am simplifying).

Now, after validation, you are ready to use your model chosen at previous step in order to predict the probability that, based on their f features, the people in Group 2 (do you remember the Group 2 defined at the beginning?) will buy the ticket in the near future. So you will have a classification model predicting the probability that the individuals out of the training and validation sample (that have not YET bought the tickets) either

• will buy the ticket (event denoted as 1)

• or they will not buy the ticket (event denoted as 0)

So you will have an estimate of the probability that the subjects in Group 2 will belong to either class.

As anticipated there is a temporal problem in the observations. So if you do not need an estimate right now, I would prefer to wait up to the next event, to be sure that those people that have not bought a ticket now will never buy one for that event. And use the whole dataset available for this event to predict those people that, at the NEXT common event, will buy the ticket. In other words, the whole current dataset would be my dataset to build predictions for the NEXT event. That would be logically more precise as you will have a certain 1-0 dependent variable for people that have bought (1) and people that never bought (0), excluding those uncertain cases of people who haven’t bought yet, but they may immediately buy before the event (solving the temporal misalignment anticipated at the beginning of the answer).

• Thank you for your answer. It's quite interesting. The tickets for the event is just an example. I should rather call them returning customers of a store or something Aug 20, 2019 at 19:43
• I have another question. How would you approach this problem if "m" is a very small percentage of the entire set N (such as m = 0.001*N)? I expect that in that case the data available for training is too small. Aug 20, 2019 at 19:45
• @DexzMen that is an incredibly right question to ask. And this may be a big problem. In an ideal world you would have tons of data that are balanced. In the real world that does not happen and poses relevant problems. Think about the following: in that case, you may have a model that, in order to maximize the accuracy, just wants to predict all the observations as 0s so that its accuracy gets 99.9% if the 1s are 1/10% of N. Which is the reason why you also want to look at what is the first type error and second type error instead of the only overall accuracy
– Fr1
Aug 20, 2019 at 20:11
• And what’s happening inside the model to the coefficients.. clearly if your number of 1s is too small, and you can’t find additional data, there are some minor measures that you can adopt, like bootstrapping maybe, and so on, but the reality is that you have a very small amount of information for your 1s which does not bode well for your estimate.. in other words you will fit a model to predict the 1s with a very small amount of info on what you are trying to predict. Which is clearly a bad situation for model interpretation, and is likely to result in an overfit. Now there are other...
– Fr1
Aug 20, 2019 at 20:14
• ... now there are other measures that you can take, but the answer does not lie into statistics.. and this is therefore where it is appropriate to stop for now
– Fr1
Aug 20, 2019 at 20:15