基于不良信息字词过滤系统的网络论坛的设计与实现外文翻译资料

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

南京信息工程大学

毕业设计（论文）外文翻译

题目： APINetworks Java—— 一种用于高效处理大 型复杂网络的Java方法

摘要

我们提出了一个新版本的应用编程接口APINetworks的核心结构包，用于处理任意计算环境中的复杂网络。新版本是用Java编写的，与以前的C 版本相比，具有以下优势：Java代码的可移植性，面向对象设计实现的容易性以及内存管理的简单性。此外，还引入了一些附加的数据结构来存储节点和边的集合。此外，通过使用目前在JVM中可用的不同垃圾收集器，Java版本比C 在存储器管理方面要高得多。特别地，由于G1和Java应用程序的并行执行，G1收集器是最有效的。使用G1，APINetworks Java优于C 版本以及建筑中众所周知的NetworkX和JGraphT软件包以及线性和完整网络的BFS遍历。当前版本的更好的内存管理允许对更大的网络进行建模。

新版本程序摘要

程序标题：APINetworks Java 1.0

程序文件doi：http：//dx.doi.org/10.17632/3pzd5v4chp.1
许可规定：Apache License 2.0
编程语言：Java
以前版本的参考：Comput。 物理 社区。 196（2015）446

关键词 ：API; Complex networks; Java; BFS; Modeling; Network science

正文

新版本是否取代了以前的版本？ 是

问题的性质：由于大数据收集的可用性，大型复杂网络的计算建模和分析正在成为一个令人感兴趣的话题。 然而，不存在任何单一的计算解决方案，可以在不同的计算环境中有效地对大型网络进行建模和分析，尤其是在网络异构和动态时。

解决方法：为了解决上述问题，我们开发了一个应用程序编程接口APINetworks，用于处理任意计算环境中的复杂网络。 通过采取面向对象，特别是继承和多态，APINetworks可以在任意计算环境中描述异构和动态网络。 最初，开发了一个C 版本的核心结构包。

解决方法：为了解决上述问题，我们开发了一个应用程序编程接口APINetworks，用于处理任意计算环境中的复杂网络。 通过采取面向对象，特别是继承和多态，APINetworks可以在任意计算环境中描述异构和动态网络。 最初，开发了一个C 版本的核心结构包。

新版本的原因：由于易于实施面向对象设计，Java版本似乎比C 更具吸引力; 代码的可移植性; 内存管理的简单性; 以及并行和分布式计算工具的可用性。 此外，使用Java的自动垃圾回收允许有效的存储器管理，对于给定量的RAM存储器，允许构建和分析更大的网络。

修订摘要：APINetworks Java版本引入了[1]中提出的一般设计的一些专门化。 特别地，我们使用有界泛型[2]来允许在网络建模类中使用整数作为节点或边缘密钥。 在这种形式中，我们可以明确地使用这些类中的关键处理方法，而不会失去泛型提供的一般性。 为此，我们引入了一个接口Indexable，定义了一个返回用于识别目的的整数的getKey（）方法。 该接口由[1]中引入的节点和边界通用接口及其所有后代类实现。 通过在给定类中定义通用类型为lt;T extends Indexablegt;，我们允许通过通用类型的任何引用使用getKey（）方法。 此功能对数据结构中的节点或边缘处理特别有用。

当使用网络上的节点时，每个节点需要存储对它们的事件边缘的适当引用。在以前的C APINetworks版本[1]中，我们使用C 标准模板库中定义的链表。在Java中，我们有一个类似的选项：在标准Java API中实现的LinkedList类。但是，LinkedList是一个双链表。所以，对列表中存储的每个元素使用两个引用：一个引用前一个元素，另一个引用到另一个元素。为了减少使用的内存量，并提高图形相关算法的效率，通常只需要遍历每个节点的边缘列表，我们就开发了一个单链表。因此，列表的每个节点仅存储对下一个节点和数据元素的引用。单链接列表APINetworksList处理实现可索引接口的任何一般元素。为了允许遍历列表，我们开发了一个迭代器。因此，APINetworksList类实现了Java标准API的Iterable接口和一个内部类APINetworksListIterator。最后一个实现了Java标准API的Iterator接口。简而言之，APINetworksList类返回一个迭代器，可以像Java API的任何其他数据结构的任何迭代器一样处理。

在以前的C APINetworks实现中，网络的一组节点和边缘可以通过通用可生长数组来表示，以及其他可能性。 然而，在Java中，数组和泛型中使用的数据模型并不完全兼容，因为数组是协变和泛型不变的[2]。 因此，不可能分配通用数组。 解决方案是分配Object类的数组并将它们转换为泛型类型。 使用我们的整数键作为数组的索引，对特定元素的访问是在不间断的时间完成的。 另外，在目前的Java APINetworks版本中，我们引入了将散列表[3]与节点或边的整数关键字作为散列码[3]。 再次，访问特定元素是在不断的时间内完成的。

目前APINetworks Java版本的另一个关键点是自动内存管理的效率。因此，我们测试在JVM中实现的不同GC的行为，使用构建完整，完全连接的网络的苛刻情况。这里，每个节点都连接到彼此。因此，对于n个节点，我们有m = n（n-1）/ 2个边缘，并且节点和边缘之间的关系是二次的，m = O（n2）m = 0（n2）。 APINetwoks Java中提供不同的数据结构，用于表示网络中的一组节点和边。在这里，我们考虑基于阵列的一个，因为数组中使用的内存访问的简单性使其成为最有效的数据结构。对于测试，我们考虑并行GC，它是当前Java 1.8分发中包含的标准配置，以及可用的两个并发GC：并行标记扫描（CMS）收集器和垃圾回收（G1）收集器。对于他们中的每一个，我们构建完整的网络，范围从103103到20·103个节点，增量为103103.结果是在具有48 GB堆内存的Octa-Core英特尔reg;至强reg;E5-2630 v3（2.4 GHz） Java API显示，G1垃圾回收器具有CMS最佳性能，最后由Parallel GC提供。我们的数据显示，垃圾收集器之间的相对差异随着网络规模的增加而增加。特别是，对于最大的网络（20·103节点），G1和CMS收集器分别仅使用平均GC时间的47％和64％。这些值分别对应于G1和CMS的加速（平均GC时间与其他收集器时间的商数）分别为2.1和1.6。

APINetworks Java的性能是针对以前的C 版本和两个流行的工具：NetworkX [4]，Python和JGraphT [5]，在Java中进行测试。作为测试，我们使用两种不同的网络操作。第一个是一个基本的：网络的建设在线性和完整的情况下。完整的案例已经介绍。在线性方法中，每个节点只链接到前一个节点。因此，对于n个节点，我们有m = n-1个边缘，并且节点和边缘之间的关系是线性的，m = O（n）m = O（n）。第二个测试使用网络的宽度优先搜索（BFS）遍历，对于n个节点和m个边缘展现O（n m）O（n m）时间复杂度[3,6]。在所有情况下，我们都将G1垃圾回收器用于Java API：APINetworks Java和JGraphT。另外，我们在Java和C 版本中为APINetworks选择了基于数组的数据结构。 NetworkX和JGraphT使用哈希表。使用JGraphT，我们使用了包内建的线性和完整的图形生成器。在所有情况下，我们构建增加大小的网络，直到系统内存耗尽。

对于线性情况，我们构建不同的网络，从106106个节点开始，并使用106106节点的增量。结果收集在图1中。 1例（a）。我们观察到运行时间与节点数量的线性关系，边缘和节点数之间的线性关系的结果（m = n-1）。在所有情况下，这种变化很适合Time = a·n类型的线性函数。最坏的情况是NetworkX具有确定系数r2 = 0.983。另一方面， 1案例（a）显示，APINetworks Java是APINetworks C ，JGraphT和NetworkX之后最为高效的包。另一方面，APINetworks Java构建了具有高达2亿个节点（67秒）的网络，而网络的8亿美元的APINetworks C ，1亿的JGraphT和5000万的NetworkX。对于使用API​​Networks C ，JGraphT和NetworkX构建的最大网络，APINetworks Java的分别为1.8,4.0和19.5倍。与NetworkX的巨大差异可归结于Python的解释性质。

对于完整的情况，我们构建了以103103个节点开始的网络，以103103个节点的步长递增大小。结果如图1所示。 1例（b）。在这里，我们观察到由于边缘和节点数（m = n（n-1）/ 2）之间的二次关系，运行时间与节点数的非线性变化。现在，变化很好地适合了类型为Time =asdot;n2的二次函数。现在，最差的情况是JGraphT，其显示出确定系数r2 = 0.923。像在线性情况下，APINetworks Java是APINetworks C ，NetworkX和JgraphT之后最有效的工具。 APINetworks Java进程在105秒内具有高达27000个节点（3.5亿个节点 边缘）的网络。该值可以与APINetworks C 的17000个节点和NetworkX的13000个节点进行比较。对于JGraphT，我们仅考虑了高达4000个节点的数据， 1情况（b），因为运行时间变得太大。对于所考虑的最大的APINetworks C ，NetworkX和JGraphT网络，APINetworks Java的分别为7.0,10.4和320.0倍。

Fig. 1.

用于构建线性网络，情况（a）和完整网络（case）（b））的时间（以秒为单位），作为节点数N和所使用的网络平台的函数。 广告代表APINetworks Java。 钻石，三角形和圆圈分别对应于APINetworks C ，JGraphT和NetworkX。

对于线性情况下的BFS遍历， 2例（a）收集比较研究结果。 首先，我们观察到运行时间与节点数的线性变化。 这是BFS程序的节点数n和边缘数m = n-1和O（n m）O（n m）渐近复杂度之间的线性依赖性的结果。 显然，在线性情况下，BFS的渐近复杂度[6]
方程式（1）
O（n m）= O（n n-1）= O（n）.O（n m）= O（n n-1）= O（n）。
打开MathJax

尽管图中观察到振荡。 2情况（a）中，四条曲线非常适合Time = a·n线性函数。 事实上，对于APINetworks Java案例，发现最差的匹配系数为r2 = 0.942。 关于相对性能， 2案例（a）显示，APINetworks Java是APINetworks C ，JGraphT和NetworkX之后的最有效的工具。 APINetworks Java需要69秒才能遍历最大的2亿个节点网络。 特别地，相对来说，APINetworks Java分别比每个包使用的最大网络的JGraphT，APINetworks C 和NetworkX快1.2,2.2和17.8倍。

Fig. 2.

用于在线性网络中执行BFS遍历的时间（秒），情况（a）和完整网络，情况（b））作为节点数N和所使用的网络平台的函数。 广告代表APINetworks Java。 钻石，三角形和圆圈分别对应于APINetworks C ，JGraphT和NetworkX。
图选项
最后，完整网络的BFS遍历结果如图1所示。 2例（b）。 现在，我们观察到运行时间与节点数量的非线性变化。 这是由于节点数n与边缘数m = n·（n-1）/ 2和BFS过程的O（n m）渐近复杂度之间的二次依赖关系。 BFS在当前案例中的渐近复杂度[6]equation(2)

O(n m)=O(n nsdot;(nminus;1)2)=O(n2)

打开MathJax

在所有情况下，结果很适合Time = a·n2二次函数。对于具有确定系数r2 = 0.901的NetworkX，获得最差的结果。现在，我们观察到，不同软件包的降序效率是：JGraphT，APINetworks Java，与APINetworks C 和NetworkX几乎相同的趋势。然而，JGraphT获得的结果一直太小。看来内置的完整网络是通过JGraphT BFS例程进行识别的，只允许对与第一个节点相邻的节点进行探索。作为一个完整的网络，这意味着所有的节点都已经访问过了。所以

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[25494]，资料为PDF文档或Word文档，PDF文档可免费转换为Word