All resources referenced in this post can be found here.
I'm a member of an online social network where you can post activities that others can join, and join activities that others have posted. Great if you want to find someone to play tennis with, or some company for your Friday night beer. Being of a curious nature I thought it would be interesting to have a look at the the composition of this network. Are there discernible subgroups, who hangs with who, and so on.
Before any analysis can be done you need some data. I'm just a member of this service so I don't have direct access to the database. Luckily the web page contains a lot of interesting data that can easily be extracted with a few regular expressions. Most importantly you can extract the activities, and which users that participated. With this information I know how many times each user have met each other user, key data for analyzing the relationships. For more details see mine.py which does the actual data mining.
The "who meets who" data can be represented as a graph. Users are the nodes, edges are the meets, and the edge weights are the number of meets. Representing the data as a graph has the great advantage of making me able to use existing graph analysis tools. produce_gdf.py stores the "who meets who" data for a specified period of time as a gdf file (a graph file format).
For the analysis I'm using Gephi which is an open source application for graph analysis. After loading the gdf file some work is needed to extract the data I'm interested in. I start by working on the layout of the graph. I want users that have met each other a lot to be close, and users that have not met each other as much to be far away from each other. This way subgroups should be clearly visible just by looking at the graph.
I'm not the first one to request this type of layout so there are a few options in Gephi. The algorithms are force based, all nodes repel each other and connected nodes also attract each other, a simulation of the forces is run and after a while the layout stabilizes at a hopefully good representation of the data. I got best results with the "ForceAtlas 2" algorithm.
The graph is full of week connections, users that have met only once or twice during the sampling period. It's hard to determine a pattern from that few meets, do these two users know each other or did they just happen to meet once or twice. To get rid of all this unusable data I filter out all the low weight edges. Below I have filtered out any edges with a weight less than 2.77 and re-run the layout. For my three months of data this leaves any relationships where the participants meet slightly less than once a month, on average.
As can be seen there are some people that meet quite often. Lets zoom in on some clusters.
101 hangs out with 577 and 350, but 577 and 350 do not hang out with each other. Looks like 101 meets 577 and 350 separately and they don't hang out as a group.
9, 121 and 13 form a strong trio. 555 almost makes the trio a quartet but lacks a connection to 121. 9 also maintains an impressive number of other unrelated relationships. On the other side 50 and 647 appear to know each other well and jointly have relationships with a number of other users, but the other users don't know each other, so it does not appear to be a very tight group.
I had to reduce the filtering quite a bit to get a more pronounced subgroup to appear. All the interconnections between the users indicates that they hang out as a group. Users in the center of the cluster are more common participants than the users at the edges of the cluster. Should be noted that since the filtering is heavily reduced these people may only have met once, so this does not have much value for the analysis. Just wanted to show how it would look if there had been any larger subgroups in my data.
So to conclude there aren't that many relationships where the participants meet more than once a month, as can be seen by the huge size reduction when filtering out low weight edges. There are two subgroups with 3-4 members and the rest are one to one relationships.
If the layout is not good enough to identify subgroups there is also an implementation of graph modularity in Gephi. The algorithm tries to split the nodes into modules which have a lot of edges inside the module and few edges leaving the module. You can color the nodes after which module they belong to, the result looks as follows.
This type of analysis is not limited to this specific case. If you have data on how people interact you can do this type of analysis. Data sources could for example be phone, mail or instant messaging metadata.
I managed to put the mined data to some practical use also, by writing a SQL query that returns the cancel statistics for a user. It returns how often, and how long before an activity, a user canceled his participation, on average. Great for estimating how likely it is you'll be drinking that Friday beer alone after all. See cancel_stats.py for more details.
python cancel_stats.py User555
Likelihood, Total event count, Hours before, User (last 6 months)
0.21, 14, 5 User555






No comments:
Post a Comment