社区(community)定义:同一社区内的节点与节点之间关系紧密,而社区与社区之间的关系稀疏。

设图G=G(V,E),所谓社区发现是指在图G中确定nc(>=1)个社区C={C1,C2,...,Cnv},使得各社区的顶点集合构成V的一个覆盖。

若任意两个社区的顶点集合的交际均为空,则称C为非重叠社区(disjoint communities);否则称为重叠社区(overlapping communities)。

SLPA(Speaker-listener Label Propagation Algorithm)算法是一种社区发现算法,它是对LPA算法(标签传播算法)的拓展。

算法思想如下:

输入参数:迭代次数T,满足社区次数要求的阈值r

输出参数:每一个节点的社区分布

(1)首先,每一个节点的存储器中初始化一个唯一的标签。

(2)然后,重复进行以下步骤,直到达到最大迭代T:

  a. 选择一个节点作为监听器;

  b. 所选节点的每个邻居随机选择概率正比于该标签在其存储器中的出现频率的标签,把所选择的标签(speakervote)发送到听众(listener);

  c. 监听器增加接收到的最流行的标签到内存。

(3)最后,根据在存储器里的标签和阈值r,后处理被用于输出社区。

 public int speakerVote() {
//Run through each element in the map to create a cumulative distribution
Set<Integer> communityIds = communityDistribution.keySet();
ArrayList<Integer> communities = new ArrayList<Integer>();
ArrayList<Integer> cumulativeCounts = new ArrayList<Integer>(); int sum=-1;
for (Integer comm: communityIds) {
sum += communityDistribution.get(comm);
communities.add(comm);
cumulativeCounts.add(sum);
} //Generate a random integer in the range [0,sum)
int rand = RandomNumGenerator.getRandomInt(sum+1); //Find the index of first value greater than rand in cumulativeCounts
int i=0;
for (i=0; i<cumulativeCounts.size(); i++) {
if (cumulativeCounts.get(i)>=rand)
break;
} //Return the corresponding community
return communities.get(i);
}

SpeakerVote

 public void updateLabels(Integer userId){
Set<DefaultWeightedEdge> incomingEdges = userNodegraph.getGraph().incomingEdgesOf(userId);//获取所有该顶点的入度顶点
Map<Integer, Integer> incomingVotes = new HashMap<Integer, Integer>();//所有speaker顶点投票情况 //For each vertex V with an incoming edge to the current node
for ( DefaultWeightedEdge edge: incomingEdges ) {
int speakerId = userNodegraph.getGraph().getEdgeSource(edge);
UserNode speakerNode = userNodegraph.getNodeMap().get(speakerId); int votedCommunity = speakerNode.speakerVote();
int votedCommunitycount = 1;
if ( incomingVotes.containsKey(votedCommunity)){
votedCommunitycount += incomingVotes.get(votedCommunity);
}
incomingVotes.put(votedCommunity, votedCommunitycount);
} //Find the most popular vote
Iterator<Entry<Integer, Integer>> it = incomingVotes.entrySet().iterator();
int popularCommunity=-1;
int popularCommunityCount=0;
while ( it.hasNext()) {
Entry<Integer, Integer> entry = it.next();
if ( entry.getValue() > popularCommunityCount ) {
popularCommunity = entry.getKey();
popularCommunityCount = entry.getValue();
}
}
//Update community distribution of the current node by 1
UserNode currentNode = userNodegraph.getNodeMap().get(userId);
currentNode.updateCommunityDistribution(popularCommunity, 1);
}

listenerUpdateCommunity

注:源代码请联系limin12891@163.com.

最新文章

  1. Android中通信协议
  2. Solaris 自动挂载
  3. NPOI Helper文档
  4. Hadoop-2.2.0 (传 hadoop-2.2.0.tar.gz)
  5. TCP/IP协议学习(二) LWIP用户自定义配置文件解析
  6. CI框架 QQ接口(第三方登录接口PHP版)
  7. Topology: The Architecture of Distributed Systems--reference
  8. php 中奖概率算法
  9. NHibernate之映射文件配置说明(转载2)
  10. 设计模式二:MVC
  11. 基于GPS数据建立隐式马尔可夫模型预测目的地
  12. wamp 3.0.6(apache 2.4.23) 403 forbidden 解决办法
  13. 还是畅通工程,最小生成树kruskal
  14. BLDC
  15. 数组-在Shell脚本中的基本使用介绍
  16. 这份书单,给那些想学Hadoop大数据、人工智能的人
  17. Java学习笔记13(equals()方法;toString()方法)
  18. webSocket开发chat application过程
  19. java工具类POI导出word
  20. 《剑指offer》第三十二题(之字形打印二叉树)

热门文章

  1. WebLogic(12C)——几个基本概念
  2. 关于java项目中的.classpath文件:
  3. ST-LINK驱动的安装
  4. xml数据改动
  5. 是什么优化让 .NET Core 性能飙升?(转)
  6. jQuery动画中stop()与 finish()区别
  7. 使用 John the Ripper 破解 Windows 密码
  8. 网络排错与网络命令的理解ping-traceroute-host(nslookup)-tcpdump获取对方的mac
  9. s21day25 python笔记
  10. .Net C# 阿拉伯数字转为中文金额数字