算法找到投票集团

Question

（警告对音乐爱好者：这与欧洲歌唱大赛的问题交易）

欧洲歌唱大赛是欧洲流行的事件。对于那些不熟悉这个概念的人来说，它基本上是一个比赛，每个参赛国都会演唱一首歌，然后为其他国家投票。每个国家可以给10个其他参赛选手奖励点数，给予他们最喜欢的歌曲12分，第二首喜欢的歌曲10分，然后8分到1分。换句话说，一个国家给予其他10个国家的分数。

我正在尝试编写一个算法来分析多年来的投票，并检测“投票集团”，即有相互投票倾向的国家。

我使用这两种类型的存储点：

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; 

有我需要回答两个问题。

1. 我该如何计算BlocScore？我需要一个衡量一群国家“友善”的好方法。对于我的prelimenary测试，我已经使用（该组中国家之间授予的积分总和）/（我希望测量的期间的年数*国家数）。这听起来合理吗？当我测试传统上被认为在ESC环境下“友好”的国家时，它似乎给了他们一个很高的BlocScore，但我不认为这是完美的。

2. 如何通过潜在区块进行循环，考虑到区域可以是任意数量的国家。我可以将自己局限于2到10个国家的集团，但我希望能够检测任何规模集团的通用算法。根据我的统计，这些年来有57个国家参加了ESC竞赛，即使我限制每个集团最多10个国家，也有超过43亿个集团。

是否有针对此特定目的的算法？还是有一些可以改编的通用算法？我试图谷歌它，但我只找到什么投票集团是的定义，而不是如何检测它们。

Answer 1

这只是与权重集群，如果我理解它的权利，所以Louvain Method可能值得检查，但它可能有点太重，因为你正在查看不到一百个国家之间的交互。

一个简单的想法是更简单：你可以将投票建模为链接，并为它们分配不同的强度，然后使用Force directed graph drawing算法来布局while图形，最后进行聚类？当然，通过查看结果，最终的可视化应该很容易进行聚类。

对于这种方法，你也可以生成一个图形文件，然后使用像Gephi这样的工具来完成它。

而且，这里有一个相关的帖子：Are there implementations of algorithms for community detection in graphs?