Algorithm to find Voting Blocs

Question

(Warning to music lovers: This question deals with the Eurovision Song Contest)

The Eurovision Song Contest is a popular event in Europe. For those not familiar with the concept, it's basically a contest where each participating country performs a song, and then cast votes for the other countries. Each country can award points to 10 other contestants, by giving 12 points to their favorite song, 10 to the second favorite song, then 8 down to 1. In other words, a country gives points to 10 other countries.

I'm trying to write an algorithm that will analyse the votes over the years, and detect "voting blocs", that is countries that have a tendency to vote for each other.

I use these two types to store the points:

TPoints = record
  FromCountry : string; //ID of the country
  ToCountry   : string;
  Year        : integer;
  Semifinale  : boolean;
  Amount      : integer; //1-8,10,12 for years 1975-present, other values for year 1957-1974
end;

TAllPoints = class(TList<TPoints>)
  //Methods i _think_ I need:
  function Sum(aFrom,aTo : string; aFromYear : integer = 0; aToYear : integer = 0) : integer;
  function BlocScore(aCountries: array of string; aFromYear : integer = 0; aToYear : integer = 0) : double;
end;

There are two questions I need answer to.

1. How should I calculate BlocScore? I need a good way to measure how "friendly" a group of countries are. For my prelimenary tests, I've used (sum of points awarded between countries in the group)/(number of years in period I wish to measure * number of countries). Does this sound reasonable? When I test for countries that have traditionally been seen as "friendly" in ESC-context, it seems to give them a high BlocScore, but I don't believe it's perfect.

2. How do I loop through potential blocs, considering that a bloc can be any number of countries. I could limit myself to, say, blocs of 2 to 10 countries, but I would like a general algorithm that detects blocs of any size. By my count, 57 countries have competed in ESC during the years, and even if I limit myself max 10 countries per bloc, that's over 43 billion blocs.

Are there any algorithms for this specific purpose? Or are there some general algorithms that can be adapted? I've tried to google it, but I only find definitions of what voting blocs are, not how to detect them.

Answer 1

This is just clustering with weights if I understood it right, so Louvain Method might worth checking out, but it could be a bit too heavy weight since you are looking at the interaction between less than a hundred countries.

One quick idea that is simpler: could you maybe model the votes as links, and assign them different strength, then maybe use a Force directed graph drawing algorithm to layout the while graph, and finally does a clustering? Of course, the final visualization should be rather easy to cluster just by looking at the result.

For this method, you could also generate a graph file, then use a tool like Gephi to do it.

Also, here's a related post: Are there implementations of algorithms for community detection in graphs?