Tag Archives: markov clustering

Determining logical project structure from commit logs

In a bored 5 minutes at work I threw the following together: Logical source file groupings in the Scala repo

The largest cluster is clearly noisy and random. I more or less expected that. But the small and medium ones often make a lot of sense.

The basic technique is straightforward: We use a trivial script to scrape SVN logs to get a list of files that change in each commit. We use this to calculate the binary pearsons of these observations to get a measure of the similarity between two files (a number between -1 and 1, though we throw away anything <= 0). We then use markov clustering to cluster the results into distinct groupings.

The results are obviously far from perfect. But equally obviously there’s a lot of interesting information in them, and the technique could certainly be refined (e.g. by looking at sizes of diffs on each file and using that rather than a simple 0/1 changed. Also experimenting with other clustering algorithms, etc). Maybe something worth pursuing?

This entry was posted in programming and tagged , , on by .

More kittens: Improving edge weight calculations

One of the problems with my old kitten clustering was that inside the black bits (text, the kitten, etc) the clustering descended into a chaotic rainbow of teeny tiny clusters.This turns out to be little to do with the clustering and more to do with the slightly moronic way I’d calculated edge weights, which was doing a bad job between dark colours. I’ve simplified the calculation, so the following should be more indicative of how markov clustering clusters this sort of thing:


The clusters are still very small, but now recognisable rather than just dots.

In case you’re wondering, this isn’t going anywhere in particular. I’m just experimenting and figured I may as well do it in public.

This entry was posted in programming, Science and tagged , , on by .