(警告音乐爱好者:这个问题涉及欧洲歌唱大赛)
欧洲歌唱大赛是欧洲的一项热门事件。对于那些不熟悉这个概念的人来说,这基本上是一场比赛,每个参赛国家都表演一首歌,然后为其他国家投票。每个国家可以给其他 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;
我需要回答两个问题。
我应该如何计算 BlocScore?我需要一种好方法来衡量一组国家的“友好”程度。对于我的初步测试,我使用了(组内国家之间的得分总和)/(我希望衡量的时期内的年数 * 国家数量)。这听起来合理吗?当我测试传统上在 ESC 环境中被视为“友好”的国家时,似乎给了他们很高的 BlocScore,但我认为这并不完美。
考虑到一个集团可以是任意数量的国家/地区,我如何遍历潜在的集团。我可以将自己限制在 2 到 10 个国家的集团内,但我想要一个通用算法来检测任何规模的集团。据我统计,这些年来有 57 个国家参加了 ESC 竞争,即使我限制自己每个集团最多 10 个国家,也超过 430 亿个集团。
是否有针对此特定目的的算法?还是有一些通用的算法可以适应?我尝试用谷歌搜索它,但我只找到了投票集团是的定义,而不是如何检测它们。
最佳答案
如果我理解正确的话,这只是权重聚类,所以 Louvain Method可能值得一试,但它可能有点太重了,因为你正在研究不到一百个国家之间的互动。
一个更简单的快速想法:您能否将投票建模为链接,并为它们分配不同的强度,然后使用 Force directed graph drawing算法来布局 while 图,最后进行聚类?当然,最终的可视化应该很容易通过查看结果进行聚类。
对于这种方法,你也可以生成一个图形文件,然后使用像Gephi这样的工具来完成。
此外,还有一篇相关文章:Are there implementations of algorithms for community detection in graphs?
关于寻找投票集团的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16906251/