Markov Cluster Algorithm (MCL) with PHP

For a recent project, I had the need to cluster groups of Twitter users. After researching several algorithms, I decided to implement Markov Clustering to see how it would go.

I wrote this in PHP as the rest of the project was in PHP and it was a good test to see if I could implement the algorithm from scratch.

The algorithm is detailed here: http://micans.org/mcl/ and an example is available here which explain it much better than I could.

The basic steps are:

  1. Create matrix representing the nodes in your graph as rows and columns with the elements representing the paths between them.
  2. Add self loops to the nodes
  3. Normalise the Matrix
  4. Expand by taking the (Expansion Parameter)th power of the matrix
  5. Inflate by taking inflation of the resulting matrix with the inflation parameter
  6. Repeat steps 5 and 6 until a steady state is reached (convergence).
  7. Interpret resulting matrix to discover clusters.

The algorithm takes two parameters in addition to the matrix, an expansion parameter (which the matrix will be raised to the power of) and an inflation parameter (which all elements of the matrix will be raised to the power of).

Once the algorithm has completed, you should end up with a sparse Matrix (full of mostly 0) and then can interpret groups by looking at rows and columns that have values at their intersection (implying they are in the same cluster).

Code is available on GitHub at https://github.com/jrowlandsnz/mcl-php

Sustain

sustain

Website: http://sustain.ca/

Description:

Website showcasing modular home building solution.

What I worked on:

  • Custom wordpress theme
  • Javascript based pricing form with PDF generation in PHP

Technologies:

PHP, Javascript, CSS

Hockey Love Hurts

hlh

Website: No longer online

Description:

Competition for Hockey Fans with Visa Cards to win a trip to the Stanley Cup final. I worked on this while employed at TBWA\Toronto.

What I worked on:

  • User signup form
  • Interact with 3rd Party email service
  • Secure admin section to set scores and select winners of select games
  • Ajax page loading

Technologies:

ASP.Net & C#, Javascript, CSS, SQL Server

Visaperks

visaperks

Website: http://visaperks.ca/ while working for TBWA\Toronto.

Description:

Website offering special deals for Visa card holders in Canada.

What I worked on:

  • Offer updates and new offers to deadlines
  • Developed templates to improve updating process

Technologies:

CSS, JSP, XML

Virtual Cricket World Cup

cricket

Description:

Competition for friends to try and pick the outcome of games in the 2007, 2011 and 2015 Cricket World Cups. For the 2015 competition the site was re-written using the Symfony2 Framework

Features:

  • User accounts
  • Ensure votes are cast before game starts
  • Leaderboard

Technologies:

PHP, MySQL, Symfony2

RSS Aggregator

nkradar

Description:

A Google News style aggregator for tech news. I developed this site to experiment with a few different things including:

  • Clustering algorithms
  • JQuery
  • Mobile Interface design
  • Database design
  • Server setup and devops

This is a project that still has a long way to go, there have been several different iterations, especially of the clustering algorithm as I experiment to find a better solution.

Technologies:

PHP, MySQL, Javascript, JQuery, CSS

Toyplanet

toyplanet

Website: http://www.toyplanet.co.nz

Description:

E-commerce website for one of the largest toy retailers in New Zealand.

What I worked on:

  • Large code and database refactor to improve performance
  • Added stock management features
  • New features as requested by owner

Technologies:

PHP, MySQL, Javascript