7,129
个编辑
更改
→社团检测算法的评价标准
如何对算法进行评价以判断哪些能够更好地检测到社团结构仍悬而未决，必须基于对已知结构的网络的分析。 一个典型的例子是”四组”测试，在这种测试中，一个网络被分成四个大小相等的组(通常每组32个节点) ，由于组内和组间连接的概率各不相同，导致出现了一些具有挑战性的社团结构，这为社团检测制造了一定难度。这样的基准图是康德 Condon 和 卡帕 Karp 的'''种植 l-分区模型 The planted l-partition model '''的特例，或者也是'''“随机块模型” Stochastic block models '''（一类包含社团结构的随机网络模型）更一般的情形。此外，还提出了其他更灵活的基准测试，允许不同的组大小和非平凡度分布。例如 '''LFR 基准测试 LFR benchmark ''' ，它是四组基准测试的扩展，包括节点度和社团大小的不同分布，能够更加严格地评价社团检测算法。
如何对算法进行评价以判断哪些能够更好地检测到社团结构仍悬而未决，必须基于对已知结构的网络的分析。 一个典型的例子是”四组”测试，在这种测试中，一个网络被分成四个大小相等的组(通常每组32个节点) ，由于组内和组间连接的概率各不相同，导致出现了一些具有挑战性的社团结构，这为社团检测制造了一定难度。这样的基准图是康德 Condon 和 卡帕 Karp 的'''种植 l-分区模型 The planted l-partition model '''的特例<ref name=PlantedPartitionModel>
{{cite journal
| first1 = A. | last1 = Condon | author1-link = Anne Condon | first2 = R. M. | last2 = Karp | author2-link = Richard Karp
| year = 2001
| title = Algorithms for graph partitioning on the planted partition model
| journal = Random Struct. Algor.
| volume = 18
| issue = 2
| pages = 116–140
| doi = 10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2
| citeseerx = 10.1.1.22.4340 }}
</ref>，或者也是'''“随机块模型” Stochastic block models '''（一类包含社团结构的随机网络模型）更一般的情形。此外，还提出了其他更灵活的基准测试，允许不同的组大小和非平凡度分布。例如 '''LFR 基准测试 LFR benchmark ''' <ref name=LFR>
{{cite journal
|author1=A. Lancichinetti |author2=S. Fortunato |author3=F. Radicchi | year = 2008
| title = Benchmark graphs for testing community detection algorithms
| journal = Phys. Rev. E
| volume = 78
| issue = 4
| pages = 046110
| doi = 10.1103/PhysRevE.78.046110
|pmid=18999496 |arxiv=0805.4770|bibcode=2008PhRvE..78d6110L}}
</ref>
<ref name="fat19">{{cite arXiv| last = Fathi| first = Reza| title = Efficient Distributed Community Detection in the Stochastic Block Model|arxiv= 1904.07494| date = April 2019 }}</ref>，它是四组基准测试的扩展，包括节点度和社团大小的不同分布，能够更加严格地评价社团检测算法<ref name=QF>
{{cite arxiv
|author1=M. Q. Pasta
|author2=F. Zaidi
|year=2017
|title=Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures
|eprint=1606.01169
|class=cs.SI
}}
</ref><ref>{{Cite journal|last=Pasta|first=M. Q.|last2=Zaidi|first2=F.|date=2017|title=Topology of Complex Networks and Performance Limitations of Community Detection Algorithms|journal=IEEE Access|volume=5|pages=10901–10914|doi=10.1109/ACCESS.2017.2714018}}</ref>。