3

（对音乐爱好者的警告：这个问题涉及欧洲歌唱大赛）

欧洲歌唱大赛是欧洲的热门赛事。对于那些不熟悉这个概念的人来说，这基本上是一场比赛，每个参赛国表演一首歌，然后为其他国家投票。每个国家可以给其他 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？我需要一种衡量一组国家“友好”程度的好方法。对于我的初步测试，我使用了 (组内国家之间授予的积分总和)/(我希望测量的期间的年数 * 国家数)。这听起来合理吗？当我测试在 ESC 环境中传统上被视为“友好”的国家时，它似乎给了他们很高的 BlocScore，但我不相信它是完美的。

  2. 考虑到一个集团可以是任意数量的国家，我如何遍历潜在的集团。例如，我可以将自己限制在 2 到 10 个国家/地区的集团，但我想要一个通用算法来检测任何规模的集团。据我统计，这些年来有 57 个国家参加了 ESC，即使我将自己限制为每个集团最多 10 个国家，也就是超过 430 亿个集团。

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

4

1 回答 1

1

如果我理解正确，这只是权重聚类，所以Louvain Method可能值得一试，但它可能有点太重了，因为你正在查看不到一百个国家之间的互动。

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

对于这种方法，您还可以生成一个图形文件，然后使用 Gephi 之类的工具来完成。

另外，这里有一个相关的帖子：图中是否有用于社区检测的算法的实现？

于 2013-06-03T21:45:59.717 回答