Friend Network Evolution

Back in February 2009, I created my Twitter account, upon the insistence of my then-girlfriend. I didn't get it. Back then, Facebook was where it was at, I didn't really get Twitter's appeal. I was pretty much just following the handful of people I knew in real life, and Stephen Fry.

So I didn't use it much. I'd pop up every now and then, post a couple tweets and give up on it again. At one point, I even developed an irrational dislike of it - whenever I saw a site had a "follow us on Twitter" button, it irked me for some reason.

But at some point, towards the end of 2009/early 2010, I gave it yet another try. I don't know why. And even when I started using it, I was resistant; still half-heartedly hating it. But what was different this time, is I started chatting with people, and I was introduced to new people.

People who don't get Twitter think it's just that thing where you can tell people when you're eating a sandwich. It's not. It's the people that make Twitter. (Tweens and arseholes notwithstanding.)

But I'm going off on a tangent.


By August 2010, I was well into Twitter - I was posting around 30 tweets per day, and I had around 30 friends*. And back then, I decided I wanted to see what my friends network looked like. So I broke out Python and the Twitter API, I pulled data, and I made the graph. Here's an updated version of it.

[click to embiggen]

Fairly small, and tidy, and relatively uncomplicated. The bulk on the right is the people I knew in real life (from school, etc.) with a few strands of new acquaintances. Note how tightly packed and interconnected they are. To the left is mostly people I met through Twitter - and in particular, through PkmnTrainerJ.

(In case you hadn't figured it out, the node and label sizes are proportional to number of connections.)

By December 2010, I decided to have a look again.

Again, this is an update of the version I originally posted; and in this case, I've tried to arrange it so that key people stay in approximately the same place.

So you still vaguely have that left-right divide, but now there's much more mixing in the middle. I'd made some new friends, but more interesting is the people who were already in the graph who formed new connections with others in my graph.

I'd also like to draw your attention to shinelikestars_ (formerly shinelikestars6) - take a look at the previous graph, can you spot him? From 2 shared connections to 8 in the space of two months. I don't think there's any sort of point I'm trying to make here. I'm just pointing it out 'cause it's interesting.


And for the next year and a half I didn't do any data collecting. It became too labourious - Twitter changed its API, so that my old code didn't work, and I had to do everything by hand.

So, the latest graph was March 2011 (technical details below). As you can imagine, a lot can happen in a year and a half.

First of all, the new people add, and the old people removed. But more importantly, look how much tighter, and how much more 'segmented' the graph is.

There are now three major groups, loosely centred on the three most connected of my friends.

On the far right are, again, the people I knew in real life. In particular, note how little that group has changed since the first graph.

In the middle, we have 'Shiney's People' - people I was introduced to by shinelikestars_. And on the left are the people I was introduced to by PkmnTrainerJ.

The smaller groups circled in red are cliques - smaller subgroups that, at least from my point of view, form their own little groupings, where (almost) everyone is interconnected. The bottom left 'clique', for example, is my parents and big sister.

And I suspect, if you were to extend the graph beyond my network, you would find that those cliques are just parts of larger interconnected groups.

In case you were wondering, PkmnTrainerJ and SallyBembridge are most connected, both with degree 14. shinelikestars_ is next most, with degree 10.

Notable disappearing nodes - Benjidoom, who deleted his account, then created a new, private one (benjirino); and AimlessAmy, who is a long story.

I should also point out that the people I follow who aren't friends with anyone else in my network do not appear in the pictured graphs. Not that they aren't as cool, they just don't join onto the graph.

* I use friend here to mean people who I follow and who follow me back. Though I would probably consider all the people in my current network (including those not pictured) friends to some degree.


Technical stuff

You can read details on how I collected the data before, in the previous blogs. But, as I say, those methods don't work anymore.

For this run, I read up on the API, and found some bits that don't need authentication to grab and manipulate.

First, you can grab a list of a user's friends with this URL

https://api.twitter.com/1/friends/ids.xml?screen_name=<username>

This will give you a list of the friends ID numbers, so you also need to use this to grab usernames

https://api.twitter.com/1/users/lookup.xml?user_id=<idnumber>

There is also a URL to check if a user follows another user

https://api.twitter.com/1/friendships/exists.xml?user_id_a=<idnumber1>&user_id_b=<idnumber2>

Which works through the browser, but I couldn't get to work in my code. So in place, I used the site DoesFollow.com; partly because it uses the URL scheme  

DoesFollow.com/user1/user2.

Which is very convenient. Though I do worry all the requests might be putting strain on that site's server.

So, putting all that together with a bit of Python, you get something like this.


A few important points:

1) It will take a while to run. I have ~50 friends, and it took well over an hour to pull all the data. In terms of computational complexity, it's O(n^2), but each of those operations takes a significant amount of time.

2) Twitter has an API limit of 150 requests per hour. The number of API requests the code will make is ~ the number of friends being looked up. I think. Which means, if you have more than 100 or so friends, this code probably won't work. Sorry. There might be a way around it, but I don't know how.

3) Obviously, this doesn't work on protected accounts. So for those people you will have to grab data by hand. Though it's not too bad for a small enough number of people.

If you do want to use the code, I've made it so you just have to change the username at the top, and run it. You will need to install Python though.

For creating the graphs, I previously use ManyEyes. But I moved to using Gephi, because it allows for more customising. The output from the code is a text file with a list of name pairs, which you can import directly into Gephi. It will build the graph for you, and then you're free to play as you like.


Aaand... Yeah, I think that's about it.


Oatzy.


[shinelikestars6 lost his red circle, on account of he isn't my nemesis anymore.]

Sorting DVDs

So there are plenty of ways to arrange your DVDs, if indeed you chose to arrange them at all. The most popular one would probably be alphabetically. Alternatives may include arranging by release date, by director, actor, genre..

At one point there was some logic to the arrangement of my own DVD. But as I got more DVDs and less space, it mostly devolved into piles, arranged roughly based on the order they were bought in, and which were watched most recently.

If I ever get time, I will re-sort them.


I accept that alphabetical may be considered 'best'. In particular, if you have a significantly large collection, it can be the most efficient approach, and makes locating any given film much easier.

Now, ordering things alphabetically is usually considered quintessentially 'OCD'/fastidious behaviour. Though there is dispute over whether liking your DVDs (and things in general) to be in order really is, or should be, considered 'abnormal'.

My point is, I could do much worse.


First of all, I think, in general, films by the same director should be kept together; particularly when it's a notable director, say, Tarantino, Kubrick, Burton.. So you could group and sort groups alphabetically by director.

I would say that films of similar genre/theme/styles should be kept close as well - noting that films by a given director will generally stay close together when this criterion is applied.

And while you're at it, why not take into consideration: actors, writers, based on works by, producers, scored by.. Basically, there are a lot of potential connections which may be considered.


So I'd like to put forward two approaches:-



1) Salesman Sort

For this approach we take into consideration 'most meaningful connections' between films, and based on that, attempt to determine which films most belong together.

So, for a given set of films, we build a network graph where pairs of films are connected if they share a common director, actors, theme, etc.

Doing this for Tim Burton films, based on actors only, will give something like this

[NB/ There may be connections missing.]

Or like this without the actor nodes

The connections between films are then weighted based on how 'meaningful' they are.

For example, Moon and American Beauty both star Kevin Spacey. Fight Club and Choke, on the other hand, have no actors in common, but were both based on books by Chuck Palahniuk. I would argue that the connection in the latter case is more meaningful - and so should get a higher weighting - than that of the former.


Now, the trick is to find a way of translating this graph into an arrangement of films. It turns out, this is as 'simple' as running a Traveling Salesman algorithm on the graph.

The traveling salesman works like this - find a path around a graph which visits every node exactly once, while minimising the distance traveled.

In our case, we actually want to find a path which (effectively) maximises 'distance', since that will lead to the more significant connections being chosen by preference.

In the above graph, the connections haven't been weighted, so we can pick any path - for example

But ideally, the connections would be weighted first so that the path (and by extension, arrangement) chosen is more meaningful.

Once a path is found, this is turned into an arrangement by simply looking at the order in which the nodes (films) are visited.


The biggest problem with this approach is forming the graph in the first place. One possible solution is to write a program which can pull details from, say, imdb to build connection. Then you'd also need to come up with some system for weighting - which may vary from person to person, depending on their particular preferences.. So it's tricky.

By comparison, the Traveling Salesman part is relatively straight forward, given that it already has well establish (if potentially slow) algorithms for solution.

This approach can also throw up some eccentricities. For example, films by a common director may be split up by a film which has few other connection elsewhere in the graph. This is why I would advise 'fine tuning' by hand.

Similarly, it's possible that the addition of new DVDs to the collection may lead to a major re-shuffle being required. Obviously, how major or minor the re-arrangement depends on how well the film fits in with your pre-existing collection.



2) Hierarchical Grouping and Associative Sorting

This is actually the approach I started out with, before it went to shit.

You might start by grouping by director. Then you might group directors by genre/theme/style. And within the bigger director groups, you might sub-group by actor. And so on..

In particular, the 'hierarchy' is constructed so that some groupings get priority over others. For example, films with the same actor might be split up when those by the same director need to be kept together. (This will depend on how you chose to structure your hierarchy).

Then, within and amongst, DVDs and groups can be arranged according to alphabet, release date, genre, .., even by colour of cover. This is where the 'associative' part comes in. Ultimately, it can come down to how your own demented logic associates and puts things together.

When I was sorting mine, I did end up with some fairly esoteric, and sometimes laboured groupings and connections in places. But you can see some overall logic in it - e.g.

Nightmare Before Christmas / ... / Sweeney Todd / From Hell / ... / V for Vendetta / ... / X-Men..

In this case - Tim Burton, Johnny Depp, Alan Moore, Graphic Novels, and so on. Note that there is overlapping between adjacent groups. They were then sub-sorted so as to be grouped by theme, and so that they formed a natural thematic progression from one group to the next (as much as possible).



Or if you prefer, you could just arrange them alphabetically. Your call..



Oatzy.


[To be honest, I wouldn't recommend either.]

Playing with Pac-Man

What the Puck?

For those unfamiliar, Pac-Man is an old arcade game, where you play as a cheese pizza trying to collect pellets while being chased round a maze by four whimsically named ghosts. Although really, if you are unfamiliar with Pac-Man, there's something wrong with you. Anyway, you can have a play online here.

The four ghost are Blinky, Pinky, Inky, and Clyde. For a good explanation of the ghosts' behaviours, here's a post from the tragically short-lived 'Game Internals' blog.

tl;dr Blinky chases, Pinky ambushes, Inky teams up with Blinky, and Clyde does pretty much whatever the fuck he wants. But really, you should read the article.

And as for the origin of the name, I'll let Scott Pilgrim explain. Or if you prefer to read, wikipedia.


Wakking Round in Circles

Graph Theory is a fantastic area of maths. Graph Theory can find you the shortest route, help you get out of a maze, tells you how to colour a map so no adjoining regions are of the same colour, to reconstruct DNA fragments, and help you find the best route for sight-seeing. Among many other things.

But sadly graph theory tends to be covered more in Computer Science courses than Maths courses. So for myself, i have to be content with books and the internet. Not that I let such thing hold me back.


So the question is this - Find the optimal route around the Pac-Man maze

What we want to do is find a route around the maze while collects every pellet. Or in graph theory terms, a route which travels along every edge at least once.

First of all, we need to turn the maze into a network graph. For this, we place a node at each junction, and join pairs of nodes according to whether or not there is a direct route between the pair.

So here's what the maze looks like, beside what the graph of that maze looks like.

The blue edges are the ones with pellets. The red edges are the ones without pellets, which you don't necessarily have to visit.

And we can assign to each edge a 'weight' - i.e. the distance (in grid squares) between the pairs of nodes

Now, first of all, we note that there are a lot of node where an odd number of edges meet (with odd degree). What this means is that the graph is not Eulerian - what that means is, there doesn't exist a route around the graph which visits each edge exactly once.

Which means that we will definitely have to travel along some paths more than once.


So the optimal path is going to be the one which minimises the total distance traveled. This is an example of the Chinese Postman Problem, and fortunately, there is an algorithm for finding the shortest route.

Without going into too much detail, what you do is pair up odd nodes, and find the shortest paths between them (using Dijkstra's Algorithm). This makes the graph Eulerian, i.e. so that a route that visits each edge at least once exists.

So if we take the bottom corner as an example, there are four node of odd degree (green).

By finding the shortest paths between pairs of odd nodes (red), we can make this mini-graph Eulerian - i.e. so all nodes have even degree. This means we can find the optimal tour around the graph (right). In this case we have to travel an additional 12 units.

Of course, it gets more complicated when you're working with the full Pac-Man graph.

When there are more than two nodes of odd degree, you also have to find the combination of pairings which minimises the total tour size. For an idea of scale, there are 20 odd nodes in the Pac-Man graph. That means there are 654,729,075 pair combinations to check and compare. And you have to run Dijkstra's algorithm 10 times for each of those permutations. It adds up.


So instead, I took the essence of the algorithm and constructed a route by hand. This is not necessarily the optimal route. For this route, you have to travel an extra 60 units - including 9 units along a path segment that doesn't contain any pellets.

There are other paths around the maze which cover (and recover) the same same ground as the above solution, and others that double back over different ground, but that add up to the same distance.

One constraint, in the case of Pac-Man, is that the path has to start at the point near the bottom of the maze, where Pac-Man starts in the game.

But also, it doesn't matter where the tour finishes (where as, the Chinese Postman starts and finishes at the same point). This means modifications to the 'optimal' solution may be possible/required.

In the bottom-corner example, we can eliminate some of the extra paths (up to 9 units worth) if we don't care where we end up.


If I ever get around to programming and running the proper algorithm, I'll let you know what the 'proper' solution is. And if you can find a better solution, let me know.


Of course what I haven't taken into account is the fact that, as you're making your way around the maze, you're also trying to avoid ghosts. I'll be honest, this path finding was more of an intellectual exercise than anything practical. You can find some strategic tips here.


This Maze Ain't Big Enough For the Both of Us.

If you follow me on Twitter, you may have already read about this - in a dream I formulated a multiplayer version of Pac-Man. But weird, subconscious machinations aside..

I looked it up on wikipedia, and there was already a multiplayer Pac-Man - Pac-Man Vs. But in that game you have one player playing as Pac-Man, and any additional players as ghosts. The aim is for the Pac-Man player to collect pellets and for ghost players to stop them. My idea is better.

First of all, you'd probably need to make the maze bigger. Each player plays as a Pac-Man, and like the normal game, their aim is to collect the most points, while trying to avoid ghosts. The game introduces a new special pellet which lets you cannibalise an opponent Pac-Man (much like the pellet that lets you eat ghosts).

Each player starts with two lives. If they lose both their lives they become a ghost. As a ghost, other ghosts can't hurt you, but you can't collect any pellets. If you catch an opponent Pac-Man, you steal one of their lives (becoming a 'living' Pac-Man again, with one life). If an opponent Pac-Man gets one of the special ghost pellets, they can eat a ghost opponent, killing them for good.

The game ends when all the pellets are collected or when all players are ghosts/dead. The winner is the player with the most points.

Or something like that.

If only I have the know how to make a real, playable version. But, hey, if there happens to be anyone out there reading this who could make it, please do..


Oatzy.

Social Posting - Part Two: We Post Together

Where were we..

So the main limit to the stripped down model in the previous post is that it only puts people into one of two states - posting, or not posting.

A more realistic model would take into account how much people are posting. The nice thing is, the change to the model is only minor - T no longer has the condition that makes its value has to be either one or zero.

The values T_i now represents the post rate of each user - that is, the number of posts posted during some arbitrary time period, n.

Here is the full, modified equation for the model

Two More Things

As you've probably noticed, we've introduced two new variables. They are:

2) Beta

Beta is a column matrix, with values represent each user's baseline post rate - that is, the rate at which a user would post if there was no-one else online - no audience, no-one to talk to.


1) Alpha

Alpha is a little more complicated. But loosely speaking, its values relate to the upper limit of each user's post rate (ignoring external effects).

It works like this: first, imagine everyone has some maximum post rate. Tbar (T with a line over the top) is the column matrix of these values. Now, suppose everyone is posting at their maximum rate. Alpha values are calculated by rearranging the model equation, thus

Any negative values in W are set to 0, since (in theory) a user has their highest post rate when any of their antagonist are not online.

What this means, is that post rates are capped by their appropriate upper limits; when all members of the population reach their maximum post rates, we find that T(n) = T(n-1) for all n - i.e. the post rates all remain constant, unless externally affected.

For technical reasons alpha is a diagonal matrix.

Alpha and Beta look like this

They won't all ways be size 4, of course. Their size will depend on the size of each particular network. The values of alpha and beta could vary over time, but for all intents and purposes, it will suffice to hold them constant.


Rainbow Graphs

Going back to the graph from last time, we might get a system equation like this

In this full model, it's not just a matter of online or offline. So instead of a series of network graphs, we represent the progression of a network as a set of line graphs.

What we find then is that the system described by this equation seems to tend towards some constant, stable point - regardless of initial conditions.

For example, with the equation described above, and starting at T(0) = [1,0,0,0] we get

And even if we start from T(0) = [100, 100, 100, 100], we get

In each case, the system converges to [15, 10, 5, 10] - Tbar - the maximum rates set when defining the variables for this system.


Interestingly, here's what happens when you set beta = 0 for all users - alpha values recalculated as [1.5, 1.11, 0.5, 1.11]

You get this weird bouncing about. It does seem like they're converging towards some fixed points. And it's converging to points roughly in proportion to Tbar, though much lower.

In fact, in online/offline form, the system looks like this

It's this early jumping on and off -line that causes the system to oscillate at first, before starting to settle down as time goes on.

We also see that, because the system starts much lower than its defined stationary point (Tbar), and because it doesn't have the boost of the base-rates, the actual stationary point the system is converging to is much lower.

If, however, T(0) were set to Tbar, then the system would have stayed constant at Tbar. Similarly, if T(0) were set to [0,0,0,0], then the system would stay there, since it wouldn't have the base-rates to get any of them off the ground.


Antagonistic Altercations

If we set up an antagonist system like that in the last post - with beta and Tbar as above, and conjugate alpha - we get a line graph that looks like this

In this case, the base-rates act to temper A's dislike of B, so that B stays online; though the result is that the stable point is lower than the maximum for everyone. The stable point for A is lowered the most.

But if we remove the base-rates (and recalculate alpha accordingly), the system progresses much like it did last time

That is, as soon as B shows up, A leaves - eventually followed by everyone else.


Upping The Tension

Now, what if we change the setup so that A and B both want to avoid each other.

One might question why two people who dislike each other would be 'friends' (in the social networking sense). I dunno. This is a hypothetical situation meant to demonstrate a point, god damn it!

Here's the system equation

Matrix of maximums, Tbar, stays the same as above at [15,10,5,10].

So if we set T(0) = [0, 10, 5, 10], here's what happens

A comes online because of their base-rate, and once they do, B disappears. Here's this system's initial and stable points

In antagonistic systems such as this and the one before, Tbar isn't a stable point.

In this case, for example, the peak rate for A occurs when B is offline and C is at their peak rate. But C is at their peak rate when both A and B are online. So if B is offline, C can't be at their peak rate, and as a result neither can A. And vice versa. So Tbar can't be achieved, since the tension between A and B pushes down the rates of everyone, themselves included.

The system does still stabilise however. It just to stabilises with B offline, and everyone else at a slightly lower rate in this case.


Now, if we do as we did in the previous blog, and take A offline (indefinitely), here's how the system evolves

In this case, the stable rates of C and D are lower than they were when B was 'forced' offline by A. And even though A isn't online, B isn't posting at their maximum rate.


Exogenous Effects

So as before, we also have to consider external effects.

People can suddenly, and unexpectedly disappear - maybe fall ill, get a job, or just not post for a while. Conversely they could find themselves in a situation where they're posting more - maybe because of a major news event, or because they're at work (procrastinating).

We can quite easily create these effects artificially, then observe how the model responds to that change. For example, we could gauge a person's importance (to a network) by removing them and seeing how dramatic an effect that has.

So in the antagonist examples above, we could say that A is more important to that network than B, since removing B had a greater (negative) effect on the C and D.


For this, we define some arbitrary function, E(n). We then multiply our model equation by this function

So for the example last time, where we removed two users C and D, then later reintroduced C, the function(s), E(n), might look like this

Or, if some major news story broke between n=2 and 5, then the function might look like this

So, if we were to, say, remove A (indefinitely) from the top system above, then the result would look like this

The important thing to note here is that even though B is the only person directly linked to A in the network, removing A from the graph lowers the rates of everyone.

Alternatively, we could double A

In this case, multiplying A by two brings everyone else's stable points up. It's also worth noting that A' stable point isn't just doubled, but multiplied by 2.7. This is a good example of the feedback effect mentioned at the start of the previous blog - increasing A' rate increases everyone else's rates, increases A' rate.

Or if we half A

In this case, everyone else' rates drop too, and A's rate stabilises at less than half it's maximum.


Agitated Antagonist

So what if we go back to our antagonist system, and start poking it...

First of all, if we half A

Then B is able to stay online, but with a stable point much lower than their maximum.

But, here's where things get interesting - if instead we double B, here's what happens

This time, they each scare each other off. But, once the other goes offline, they each come back in the next turn, only to scare each other off again. And so on. And all this jumping between extremes makes C and D jump about as well, but half a cycle out of sync.

At least, that's what happens for initial conditions [0, 10, 5, 10]. If we start with all at 0, the behaviour is nearer to that with no external effects.


In General

So it seems to be the case that externally changing one user affects (almost) everyone in the graph.

That being said, I would expect that when the model is generalised to much larger networks, we would find that the greater the distance between two users, the less affect they will have on each other.

It probably stands to reason then that, for a given user, it's only worth considering a graph as wide as friends of friends. Maybe friends of friends of friends for (a collection of) dramatic changes at that distance.

More in general, when you apply the model to a system of more than four people (as we've looked at here), you would expect things to get more complicated.

But the overall results should be similar - that is, in most cases the system will tend towards some stable state. It may just take longer to reach that point, depending on the size of the graph.


In Conclusion


So the long and short of it is this - in most cases, a group's post rates will typically converge towards some stable point.

If there aren't any antagonists, and if the base-rates aren't zero for everyone in the network, then the stable state will typically be the common maximum, Tbar. Otherwise, the system may oscillate, or else become stable at a much lower set of rates.

If we set all base-rates to 0, we find that the systems behave much like they did in the simplified online/offline model discussed in the previous blog; with some quirks of their own.

In the absence of base-rates, or in the presence of antagonists, initial conditions become important, affecting if and where the system stabilises.

When we consider external effects, the same will tend to be true - but with the stable points altered, according to what that effect is.

Modifying one user affects everyone else in the graph (to some degree). Modifying different users will have different effects on the rest of the graph, depending on the 'importance' of that user.

Of course, in the real world, external effects are unpredictable, and will tend to keep the system off-balance (unstable). But we do what we can.


Oh, and if you were wondering how I got the numbers for the graphs, here's the code I used. But be forewarned, it's very sloppy.


Oatzy.


[..and the fundamental interconnectedness of all users.]

Social Posting - Part One: Who's Online?

Coherence of Absence

So imagine it's Sunday, there's nothing to do, nothing's open, nowhere to go, nothing on TV. So why aren't people spending all this free time online - tweeting, Facebooking, whatever?

Sunday is an online dead-zone.

A random hypothesis I thought up to explain this, posits that this may be the result of large numbers of people thinking "why post, if there's going to be no-one around to see it?". After all, no-one's around on Sunday. If they were, they'd be posting stuff.

I called it Coherence of Absence, because a fancy name can make a daft idea sound respectable. The alternative was The Sunday Effect.

Of course, it could be that people mostly social network when they're at work (procrastinating). Or maybe they're asleep/hungover on Sunday. Or have nothing to talk about, since Sundays are so boring. I dunno. I'm unemployed, so Sundays aren't much different to any other day of the week.


In Other Words

So this can be boiled down to two principles:

1. People are likely to post more when there are more people online

2. The number of people perceived to be online at any given time is based on who is posting

It's fairly intuitive that when there are more people online (posting), you'll post more - not just because there are more people to talk to - tweets to reply to, posts to comment on - but also because there's a bigger audience; more people to see what you have to say, regardless of how interesting or mundane that might be.

In essence, these two together create a feedback effect where your posting habits are based on your friends' posting habits, are based on (to some extent) your posting habits. And so on.

For point two, we can't generally say for sure whether or not someone is online, except for when they post something. Though there are exceptions. Of course, the irony of this model is that it assumes that everyone is online all the time - just waiting for someone else to indicate their presence with a post.

Don't get me wrong, I'm not saying this is definitely how the world works. This is more of a, let's suppose this is how it works - what then?

NB/ the people a user follows are referred to as 'friends', since 'the people a user follows' is such a mouth full. These imaginary people may not, strictly speaking, consider each other friends.


Technically

Right, let's dive in: for some network of users, define a matrix M with entries

For example

NB/ connections between users needn't necessarily be two-way (except in the case of Facebook).

Next, we define a column matrix, T(n), with entries

Now, we say that if at least one of a user's friends is posting, then the user will 'come online' and post in the next turn. Vice versa, if none of their friends are posting, then the user will 'go offline' and not post in the next turn.

To do this mathematically, we just multiply the matrix M by the matrix T. For example, if we start with only B online (blue),

Then, as expected, all the people who follow B come online. B goes offline since none of the people they follow were online in the previous turn.

You'd then multiply M by T(1) to get T(2), M by T(2) to get T(3), and so on. Here's another example, starting with only A online,

Easy.


That's Not Normal

The problem with the model so far is that there only needs to be one other person online for a user to join them. But one person online will be more significant to a person following 5 people, than to a person following 100.

So we might instead say, if at least half of a user' friends are online, then the user will join them in the next turn. First of all, we define a matrix, W, with entries,

So for the example above, we get

That is, the matrix M normalised so that the sum along each row equals 1. Our definition of T then becomes

Which is just a fancy way of saying, if at least half of a user' friends are posting, then the user will post in the next term.

So, for example, if we start with A and D online,

As before, everyone ends up online. But in this case, if we had started with only A online, then that means only a third of B' friends are online, so B wouldn't come online in the next turn. Nor would anyone else, for that matter - everyone ends up offline.

Of course, you could change it so that a user will come online if a third, or a fifth, or whatever of their friends are online. If you really wanted to.


Weightlessness

Of course, this supposes that a user cares about all their friends equally. In reality, we might care more about one person being around than another. There may even be people we don't care about at all (in terms of what we post), or people that we want to avoid.

The trick is this - instead of assigning everyone a 1 in the matrix M, let user i assign to each of their friends, j, some numerical weighting, based on how much i cares about j. If i prefers to avoid j, then this value may be negative.

Call this matrix W'. This matrix is, again, normalised to generate W, as before; making the sum along each row equal 1. The only difference is that with antagonists, some rows may add up to 0. So to avoid division by zero we have this

At this point, I'll introduce the equation for the model so far

Avoid the Antagonist

So let's say this is our network now, with accompanying normalised-weighting matrix

B has no qualms with A, but for whatever reason A harbors some secret dislike of B, and will typically want to avoid them. Why does A still follow B? Keeping up appearances, stalking? I dunno. Let's just pretend there's a good reason.

So, for example, if we start with A, C, and D online, here's what happens

B comes online because both their 'friends are online. But B coming online effectively scares everyone else off, one by one. Admittedly, that's partly because I specifically chose weightings that would cause this to happen. But you get the idea.

Of course, once B goes offline, A might decide to come back online again, with D and then C following shortly after. At which point, we end up back at the start (1), where the cycle repeats.


Can't Talk

For this we go back to the first graph above, weightings all the same. Say one or more of the users go offline - maybe they're out on the town, or asleep, or something of that sort. What then?

If we take just one person offline, then nothing will happen to any of the other users - except if you remove B, in which case only A goes offline. So in the below example we take C and D offline (red)

By (4) everyone is offline, so that when D comes back online at (5) there's no-one else online to keep them around. And D alone isn't sufficient to bring anyone else back online.


Wait For It

So this is a very simplified model. For one thing, it only considers people as either online or offline - or if you prefer, posting or not posting. It also assumes that, in the absence of an 'audience', a person won't post. And that leads to the implication that a social network can be destroyed by strategically removing users. It can't. I don't think.

Anyway, til next time..


Oatzy.

Tumbling, Appendix I: Making Connections

Where Things Get Interesting

Recall in Part 3 (under 'Notes and Improvements'), I mentioned the possibility of creating graphs of how a post spreads - ie who reblogged who.

As it turns out it was possible. And in fact, not that difficult.

You can find the modified code here.

In addition to the outputs the previous iteration generated, this updated version also creates a 'graph.csv' file, which contains all the links between reblogging users. This file can then be imported into, for example, Gephi, to create a visualisation of the graph.


Modified Model

The updated model works thing like this

We have the set, F, of people who reblogged in the previous generation. For each of these users we iterate over their followers, with the reaction code as before.

But we now have the addition that, if the follower reblogs, a new property - user.reblogged - is set to the person they reblogged from. That (reblogging) user is then added to the temporary group f_i to be used in the next iteration.

The simulation ends when f_i is empty - ie, no-one reblogs.


Pretty as a Picture

So, keeping the initial conditions the same as for Part 3, here is an example output

And here if the accompanying 'spread over eccentricity' graph.

Compare for those visualisations in Part 1

I have to say, I am extremely pleased with this. I mean, just look at it! It's amazing.

Here's another example

And finally, here's a graph for a population size, N = 20,000 & f0 = 1,000

More reblogs overall, and lots more clustering in this case. Pretty awesome, right?


Little Niggles

The only things that really bother me now:

1) The Like count seems a little high
This is probably a result of the distribution/variables chosen in creating approval thresholds.

2) There's only a small number of reblogs coming from OP.
This relates to the 'reblogs from tags' thing discussed in Part 3.

3) Small population
At some point, when I've got the time to run the simulation, I'd like to try it with larger populations/larger f0

But none of these things bother me too much, and I'm pleased with what I've got.


So that's basically that.


Oatzy.