一个新的基于图表的社区检测算法
Pablo M Redondo1, Reza Mousapour2, Wayne B Hayes1
1Department of Computer Science, University of California, Irvine, California, USA.
概括
这项研究引入了一种新的社区检测算法,使用图形来找到网络中更密集和更大的社区. 这种新方法在生物和社会网络分析方面显著优于现有的方法.
科学领域:
- 网络科学 网络科学
- 计算生物学是一种计算生物学.
- 数据挖掘是一种数据挖掘.
背景情况:
- 社区检测是各种应用的网络分析的一个关键问题.
- 现有的算法面临着挑战,原因是问题的NP完整性和缺乏黄金标准定义.
- 定义基于统一,高边缘密度的社区提供了一个强大的方法.
研究的目的:
- 引入基于图形采样的新型社区检测算法.
- 为了证明算法的优越性能在寻找密集和大型社区.
- 在生物网络中验证算法的有效性,包括与DREAM挑战获胜者进行比较.
主要方法:
- 该算法通过采样图片 (小型诱导子图) 来识别社区,其边缘密度高于指定的值 (ε).
- 这些图片凝聚在一起并合并,形成具有均高边缘密度的社区.
- 该方法与各种网络类型的现有算法进行了验证,特别是来自2016年DREAM挑战的生物网络.
主要成果:
- 新的算法在检测重叠社区方面始终优于现有方法,产生更大,更密集的社区.
- 在生物和非生物网络中评估了性能,显示出近乎普遍的优越性.
- 在2016年的DREAM挑战中,相比于获奖项目,该算法识别出了比较密集的社区.
结论:
- 拟议的基于图形的社区检测算法比现有方法有了显著的进步.
- 它发现均密度和大群体的能力使其在网络分析中非常有效,特别是在生物环境中.
- 该算法的强性能验证了基于边缘密度的社区的拟议定义.
相关概念视频
Vector Algebra: Graphical Method
14.0K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
14.0K
Cluster Sampling Method
12.8K
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
12.8K
Ogive Graph
5.9K
An ogive graph is sometimes called a cumulative frequency polygon. It is one type of frequency polygon that shows cumulative frequency. In other words, the cumulative percentages are added to the graph from left to right. An ogive graph plots cumulative frequency on the vertical y-axis and class boundaries along the horizontal x-axis. It’s very similar to a histogram; only instead of rectangles, an ogive displays a single point where the top right of the rectangle would be. Creating this...
5.9K
Multiple Bar Graph
7.9K
As the name suggests, a multiple bar graph is the same as a bar graph but has multiple bars to depict relationships between different data values. One can include as many parameters as possible. However, each parameter must have the same unit of measurement.
Each bar or column in the multiple bar graph represents a data value. These graphs are used primarily in interrelating two or more sets of data. The categories of different kinds of data are listed along the horizontal or x-axis, whereas...
Each bar or column in the multiple bar graph represents a data value. These graphs are used primarily in interrelating two or more sets of data. The categories of different kinds of data are listed along the horizontal or x-axis, whereas...
7.9K
What are Populations and Communities?
34.9K
Overview
34.9K
Time-Series Graph
4.5K
A time-series graph is a line graph with repeated measurements taken at successive intervals of time. It is also called a time series chart. To construct a time-series graph, one must look at both pieces of a paired data set. The horizontal axis is used to plot the time increments, and the vertical axis is used to plot the values of the variable that one is measuring. By using the axes in this way, each point on the graph will correspond to time and a measured quantity. The points on the graph...
4.5K


