认识:一个复杂的网络数据分析的框架

文摘

网络数据挖掘以来吸引了很多关注,很多现实问题需要处理复杂的网络数据。在本文中,我们目前的认识,一个开源框架,基于网络的数据挖掘。认识特性的大量技术和方法分析结构网络的属性,网络可视化、社区检测、链接得分,链接预测。拟议的框架被设计在坚实的设计原则,利用并行计算使用结构化的并行编程。认识还提供了一个独立的图形用户界面允许使用先进的软件分析技术的用户没有编程经验。这个框架是可用的开源软件BSD许可协议。

1。介绍

数据挖掘、计算机科学中的一个跨学科的领域,研究的过程,从数据中提取有价值的信息通过发现模式或关系。数据挖掘包括分类、回归、聚类和异常检测等任务(1]。大量的工具和技术可用于表格数据,所有数据例子可以表示为元组关系和他们共享同一组属性。然而,许多问题涉及处理关系数据,明确相关实例通过语义关系。经典的数据挖掘技术设计了表格数据有严重的局限性,当我们试图充分利用可用的关系在关系数据。科学界一直专注于关系数据的数据挖掘技术的发展,导致大量的可用性的技术分析网络的结构属性(2),他们愉快的可视化3],现有社区的检测[4,得分现有或潜在链接到现有的排名或预测他们的存在5,6]。网络数据挖掘涉及不同的问题。一些例子包括未知的蛋白质相互作用的预测蛋白质相互作用网络(7),协作和倾向的预测coauthorship网络(8),或根据用户查询最相关的网站排名(9]。

不同的软件工具分析关系数据开发,根据他们的主要目标和用户定向到的类型。几个工具向最终用户提供的功能通过封闭的图形用户界面,从而提高可用性,也忽视了使用提供了技术的可能性,以不可预见的方式通过他们的软件开发人员和集成在其他软件项目。其他工具被设计成软件库,可以使用不同的软件项目,提供更多的功能为代价的限制他们的使用有编程经验的用户。

大多数现有的框架是关注于一个特定的用户社区或任务,如表所示1。例如,Graphviz [10]和Cytoscape [11是网络可视化的两个受欢迎的选择。相反,igraph [12],NetworkX [13),和快速14)主要集中在提供可重用的集合算法进行网络操作和分析。Pajek [15],NodeXL [16],Gephi [17],UCINET [18)是最广泛使用的一些工具对社会网络分析(SNA)(一个更全面和最新的可用网络分析软件工具的列表可以在维基百科:https://en.wikipedia.org/wiki/Social_network_analysis_software)。

在本文中,我们介绍认识(网络探索、模拟和感应系统),宽容的BSD开源许可下发布的软件框架分析和挖掘复杂网络。认识是建立在一套结构化的并行编程的设计模式,提供大量的网络挖掘技术能够利用多个处理核可以在当前微处理器更有效的计算。我们的框架是完全用Java编写的,这意味着它是便携式的,在不同的硬件和软件平台,包括Java虚拟机提供。此外,我们提供了一个API为Python绑定,使认识从Python脚本语言的使用,经常使用的数据科学家。

我们的论文结构如下:在部分2,我们描述和讨论认识架构和设计。在部分3和4中可用的网络分析和网络挖掘技术,提出了认识。节5,认识性能比其他受欢迎的网络分析工具。最后,我们的项目部分中描述的现状和未来的发展方向6。

2。设计的认识框架

理智被设计成为一个容易扩展框架的体系结构提供了实现的基础网络的数据挖掘技术。为了实现这一目标,理智是围绕抽象接口和一组核心类,提供必要的功能,它允许不同的特性作为独立的组件的实现,并有很强的凝聚力和松散耦合。认识组件设计成可维护和可重用,而高效。

2.1。系统架构

认识框架体系结构和其核心子系统是显示在图1。下面将描述这些子系统。

体现组件是硬件抽象层(HAL)提供支持的执行算法在并行环境和隐藏实现细节和底层技术的复杂性。此组件提供不同的构建块来实现研究并行编程设计模式,如MapReduce (19]。例如,我们只会写结果=(双)平行。减少(索引- - - - - -> x(指数)∗y(指数),添加,0,大小是1)并行计算两个向量的点积。哈尔不仅实现了结构化并行编程设计模式还负责任务调度和并行执行。它允许并行执行参数的调整,包括任务调度算法。

反光内核的核心认识,并提供其主要特性。反光内核提供了基本模型(数据结构)和任务需要执行网络数据挖掘(算法),以及相应的metaobjects和元模型,在运行时可以操纵。它是底层层,支持大量的网络分析算法和数据挖掘技术,这在下一节中描述。不同类型的网络处理使用一个统一的接口,允许我们选择最适合的特定实现的空间和计算每个应用程序的要求。这个子系统提供的算法是建立在哈尔的构建块,允许并行执行算法。

数据访问层(DAL)提供了一个统一的接口来访问外部数据源。这个子系统允许读和写网络在不同的文件格式,为一些最重要的标准化提供了实现网络文件格式。这个模块还支持数据访问组件的开发其他类型的数据源,如网络流。

最后,应用程序生成器用于构建一个完整的图形用户界面模型驱动软件开发(MDSD)方法。此组件提供了一个用户友好的界面,允许用户没有编程技能用的最多的认识框架的特性。

2.2。核心类

核心类和接口如图2为不同类型的实现提供了基础的网络与特定空间和计算的要求。基本的网络操作包括添加和删除节点,添加和删除链接,或查询节点附近。通过专门的组件提供了更复杂的操作。

面向对象的纯粹主义者可能会感到惊讶,节点和链接没有明确显示为节点和链接类中认识的核心类。这明显违反了OO设计原则有一个垃圾收集技术理性性能下降的编程语言(如Java、c#或Python)由于增加内存碎片。在处理大型网络时,在堆中数以百万计的单个对象的存在会显著增加内存碎片和降解垃圾收集器的性能。因此,节点和链接是不被认为是核心类在理智,虽然他们肯定可以在需要的时候使用(轻质外墙底层网络数据结构封装在特定网络子类)。

理智支持网络节点和链接属性。这些属性定义根据预定义的数据模型,包括分类和数值。

2.3。支持的数据格式

网络数据集提出了不同的文件格式。有些数据格式空间效率更高,而其他人更容易解析。

理智支持阅读和写作网络数据集使用最常见的数据格式。例如,GDF文件格式是一种CSV-like格式所使用的一些软件工具,如猜和Gephi。它支持属性节点和链接。另一个支持的文件格式是GML,即图形建模语言。GML分层ASCII-based文件格式。GraphML是另一个分层的基于XML的文件格式,无处不在的可扩展标记语言由W3C开发。

其他文件格式支持的认识,比如Pajek文件格式,这是与GDF相似,或者是文件格式的数据集从斯坦福大学网络分析平台(临时)20.]。

2.4。图形用户界面

为了允许用户没有编程知识用最理智的特性,一个轻量级的易于使用的图形用户界面包含在标准的认识框架。认识GUI允许加载非技术终端用户,可视化,并分析自己的网络数据集通过应用技术提供了认识。

该GUI的一些截图如图3。帆布是用于显示网络在每一刻。网络可以通过点击或拖动操作节点。在窗口的顶部,一个菜单给访问不同的选项和数据挖掘算法。的网络菜单允许加载网络从外部源和输出结果使用不同的文件格式,以及当前网络的创建图像可视化作为光栅图形(PNG和JPEG文件格式)的位图和矢量图形(SVG格式)。的视图菜单允许网络的定制外观通过设置特定的布局算法和自定义可视化风格。此外,这个菜单允许绑定的视觉属性节点和链接到它们的属性。的数据菜单允许勘探的属性为每个节点和链接。最后,分析菜单提供了访问的大多数技术将在以下小节中描述。

3所示。网络分析工具

理智是为了缓解网络分析工具的实现。它还包括大量流行的可重用的实现网络相关技术,从图形可视化3)和通用图算法网络结构属性(21)和网络形成模型(22]。网络分析工具包括在认识和实施这一节介绍的模块。

3.1。网络模型

认识实现了很多流行的随机网络的生成模型,用概率分布来描述或随机过程。这样的模型被发现是有用的研究和理解的某些属性或行为中观察到的现实世界的网络。这些模型如图的一些示例4。

模型中包含在理智,Erdos-Renyi模型(23)是一种最简单的。吉尔伯特模型(24Erdos-Renyi模型类似,但存在的概率是给定的链接。固定网络模型也类似于前两个模型,与减少出现孤立节点的优势,但代价是小于完全随机的。锚定连接随机模型是一个变化的模型,该模型避免了孤立节点。

其他模型包含在认识展示特定属性经常发现在实际网络。例如,Watts-Strogatz模型[25)生成网络具有小世界特性,即低直径和高聚类。这个模型开始通过创建一个环晶格与给定的节点数量和给定的学位,其中每个节点连接到双方最近的邻国。在以下步骤中,每个链接关联的是一个新的目标节点与一个给定的概率,避免self-loops和链接重复。

尽管网络的小世界特性表现出Watts-Strogatz生成的模型更接近实际网络性能比基于Erdos-Renyi方法生成的模型,他们仍然缺乏一些重要的属性中观察到真正的网络。Barabasi-Albert模型(26)是另一个著名的模型,生成网络的节点度分布遵循一个权力法律,导致无标度网络。这个模型是由一个优惠附件的过程,添加新节点和连接到现有节点的概率与他们当前的程度成正比。另一个模型具有非常相似的属性Barabasi-Albert模型价格的引用模型(27]。

除了随机网络模型,一些常规的网络模型是包含在理智。这些模型生成合成网络有用的过程中检测新算法。常规网络模型包括完整的网络,所有节点相互连接;星形网络,所有节点都连接到一个中心节点;环网络,每个节点连接到最亲密的两个邻国沿着环;串联网络,像环模型,但没有关闭循环;网状网络,节点按行和列,只连接到他们的相邻节点;环面;网格,网格的节点在极端连接;超立方体; binary trees; and isolates, a network without links.

3.2。网络结构属性

网络结构属性允许量化的特性或行为出现在网络。他们可以被使用,例如,测量网络鲁棒性或揭示重要节点和链接。理智考虑三种类型的结构属性:节点属性,节点对属性(有或没有对两人之间的联系),和全球属性。

认识提供了大量的技术分析网络结构属性。许多结构属性计算节点。例如,入度和出度表明传入和传出链接的数量,分别。节点相关学位,两种技术来测量节点度assortativity已经包括:偏见(28和公正的29日学位assortativity]节点。节点assortativity得分之间1,措施对连接节点之间的相关程度。节点的聚类系数也可以计算。一个节点的聚类系数是邻国的分数也连接在他们中间。

可达性分数中心措施,允许的分析是多么容易达到一个节点与其他节点。的偏心节点被定义为任何其他节点的最大距离30.]。然而,亲密的倒数之和距离给定节点到所有其他节点(31日]。调整后的亲密值,可实现显示亲密的数量可及节点也可以使用。反向亲密,平均路径长度的定义是所有最短路径的平均距离到其他节点。衰减是另一个可达性得分,计算的总和三角洲因素由任何其他节点的路径长度22]。有趣的是,接近0,三角洲因素测量变得节点的程度,而三角洲接近1,组件的测量成为大小节点位于。规范化的衰变分数也可以。

中间状态,可达性,是另一个衡量节点中心的方法。中间状态,也称为弗里曼的中间状态,是一个得分计算最短路径的计算节点参与(32]。因为这个分数范围从来为节点的数量n在强连通网络,通常使用标准化的变体。

影响算法提供一个不同的视角对节点中心。这些技术测量每个节点的力量来影响他人。最受欢迎的算法是影响PageRank (9),因为它使用的是Google的搜索引擎。PageRank计算概率分布基础上的可能性达到一个节点从其他节点。算法通过迭代更新基于直接邻居节点概率概率,从而导致收敛如果网络满足特定的属性。打一个类似的算法(33),即hyperlink-induced主题搜索。PageRank它遵循迭代方法,但计算两个分数每个节点的中心,这是一个得分多少节点相关的特定节点链接,和权力,这是一个得分多少中心相关链接一个特定的节点。分数都是连接通过迭代更新过程:机关更新分数据中心传入链接,连接的节点,并根据权威中心更新分数由外部链接的节点连接。特征向量中心是另一个迭代法PageRank密切相关,在节点分配一个中心得分基于邻居节点的中心的总和。Katz中心考虑所有可能的路径,但惩罚长句子使用给定阻尼因子(34]。扩散中心(35算法基于Katz中心)是另一个影响。主要的区别在于,当Katz认为无限长的路径,给定有限的扩散中心只考虑路径长度。

在以下Java示例中,我们展示了如何从一个数据文件加载网络和计算使用认识其结构特性,特别是其网页排名分数:FileReader FileReader = new FileReader (“karate.gml”);NetworkReader读者= new GMLNetworkReader (fileReader);网络网络= reader.read ();PageRank任务= new PageRank(网络);NodeScore得分= task.call ();

我们还展示了如何使用Python的理智API:实现这个例子ns =理智()network_reader = ns.create_network_reader (GML)网络= network_reader.read (“karate.gml”)pagerank_scorer = ns.create_node_scorer (“PageRank”)成绩= pagerank_scorer.compute(网络)ns.end ()

除了前面提到的中心措施,理智还提供了现成的实现渗流中心(36)和cross-clique连接(37),确保所有主流中心提供的措施是我们的软件平台。除了常见的中心措施,理智可以计算鲁棒性系数(38]分析复杂网络的结构鲁棒性,这是特别有用的评估目标攻击的场景。

不同的结构属性链接也可以计算通过认识,例如,中间性的联系,这是最短路径的计算链接参与,或链接射线,这是可能的路径交叉的两个节点之间的数量给定的链接。其中一些属性使用不同的网络数据挖掘算法。

3.3。网络可视化技术

人类仍然比机器视觉识别特定的模式在分析数据。网络可视化是一项复杂的任务,因为网络往往是巨大的,与数千个节点和链接。理智使网络的可视化提供了所需的功能呈现网络和使用不同的图像文件格式导出结果的可视化。

认识提供了不同的自动图布局技术,如著名的Fruchterman-Reingold [39]和Kamada-Kawai [40(见图)部队布局算法5)。部队布局算法对节点之间分配部队和解决系统达到一个平衡点,这通常会导致一个审美可视化。

分层布局(3),安排节点层试图减少边缘交叉,也包括在内。不同的径向布局算法也包括(42]。这些布局类似等级的但在同心圆排列节点。几个固定的布局提供了常规网络可视化的因为他们是常见的,如网格或星星。

理智可以调优网络可视化外观和感觉。的视觉属性节点和链接可以定制,包括颜色、大小和边界。此外,视觉属性可以绑定到静态或动态网络的属性。例如,节点的大小可以绑定到一个特定的中心得分,允许定量信息的视觉显示。

认识提供了一个交互式图形用户界面,可用于探索中等规模的网络和测试结果不同的方法使用一个易于使用的拖放界面提供。这个补充的工具可用于分析小数据集和教学课程。当前版本的认识包括JavaFX网络利用硬件加速渲染器,同样的技术受雇于其他网络与强大的专注于网络可视化分析工具,如Gephi或Cytoscape。的理智JavaFX-based网络渲染器提供了相同的性能收益,也可以通过其他工具,利用硬件加速(例如,Gephi)。然而,值得注意的是,补充UI工具包括在理智分布并非设计用于处理大型网络,因为它通常是不切实际的想象与数以千计甚至数以百万计的网络节点和边million-pixel电脑屏幕。认识提供Gephi-like性能和视觉导航真正的大型网络,专业的解决方案,如Cytoscape,推荐。在这种情况下,网络数据分析,编程的认识应该使用API而不是交互式探索工具。

4所示。网络数据挖掘技术

网络数据挖掘技术存在的无监督和监督设置。认识包括一系列广泛的社区检测方法4)和链接预测技术(43]。下面简要描述这些算法。

4.1。社区检测

社区检测的任务可以被定义为寻找紧密连接节点的组。广泛的社区检测算法已经提出,表现出不同的优点和缺点。理智特征不同家庭的社区检测技术和实现了十多受欢迎的社区检测算法。这些社区检测技术的一些示例图所示6。包括算法,时间复杂度和书目引用表所示2。

认识提供了分层聚类算法。会凝聚的层次聚类将集群作为集群每个节点,然后迭代合并,直到所有的节点都在同一个集群(56]。不同的策略选择的集群实现了合并,单键方法(包括45),选择最小的两两距离最小的两个集群;complete-link方法(46),选择最小的两个集群最大两两距离;和average-link方法(47),选择距离最小的两个集群平均成对。

Modularity-based技术也可以在我们的框架。模块化是一个分数,措施的强度特定划分成模块的一个给定的网络。Modularity-based技术寻找社区试图最大化他们的模块化成绩(57]。不同的贪婪策略,包括快速贪婪(48和多步贪婪49),是可用的。这些贪心算法合并对集群最大化产生的模块化,直到所有可能的合并将会减少网络模块化。

Partitional集群是另一种常见的方法。划分聚类分解之间的网络和节点执行迭代迁移集群。例如,Kernighan-Lin分为两部分(50]从任意划分成两个集群。然后,迭代节点之间交换两个集群减少它们之间的链接的数量。这种方法可以应用多次细分获得的集群。k - means社区检测(51是传统的k - means聚类算法的一个应用网络和分区社区检测的另一个突出的例子。

光谱社区检测(56)是另一个家庭的社区检测技术包括在理智。这些技术使用网络的拉普拉斯算子表示,这是一个网络表示法计算减去网络的邻接矩阵的对角矩阵,每个对角元素等于相应的节点的程度。然后,网络的拉普拉斯算子表示的特征向量计算。认识包括比例削减(EIG1)算法(52),约旦和维斯NG (KNSC1)算法(53),光谱k - means (54]。

BigClam重叠社区检测器也可以在认识(55]。在该算法中,每个节点有一个概要文件,包括在每个集群的分数在0和1之间,正比于节点属于集群的可能性。也得分对节点之间定义屈服值正比于其聚类任务重叠。每个节点算法迭代优化概要文件连接节点之间的价值最大化和最小化之间的价值无关的节点。

在以下的示例中,我们展示了如何从一个数据文件加载网络使用理智和检测社区KNSC1算法:FileReader FileReader = new FileReader (“mynetwork.net”);NetworkReader读者= new PajekNetworkReader (fileReader);网络网络= reader.read ();CommunityDetector任务= new NJWCommunityDetector(网络);矩阵结果= task.call ();

同样的例子也可以在Python中使用Python的理智API编码:ns =理智()network_reader = ns.create_network_reader (“Pajek”)网络= network_reader.read (“mynetwork.net”)community_detector = ns.create_community_detector (“NJW”)社区= community_detector.compute(网络)ns.end ()

4.2。链接得分和预测

链接得分和链接预测是两个密切相关的任务。一方面,链接得分的目的是计算一个值或重量显示一个链接到一个特定的标准。大部分的链接得分技术获取这个值通过考虑重叠或两端节点的邻居之间的关系的链接。另一方面,链接预测计算一个值,体重,或者概率成正比的可能性的存在某些链接链接形成的根据一个给定的模型。

认识框架提供了大量链接得分和链接预测方法,从本地方法,只考虑直接邻居节点的通用方法,考虑整个网络拓扑结构。一些例子如图所示7。考虑增加的信息量,计算和空间技术的复杂性也增加。链接得分在认识和预测方法如表所示3。

在当地的方法,最基本的技巧是常见的邻居分数(59),的数量等于邻居一对节点之间共享。最常见的技术变化的邻居得分。例如,Adamic-Adar分数(60)的总和除以每个共享节点的度的对数。资源分配指数(61年]遵循相同的表达式,而是直接认为学位对数的学位。自适应惩罚程度评分(62年也遵循相同的方法但自动确定一个适当的处罚程度通过考虑网络拓扑的属性。当地其他措施考虑共享邻居的数量,但根据一定标准规范化的价值。例如,Jaccard分数(63年)可实现共享邻居的数量总数的邻居。当地Leicht-Holme-Newman分数(64年)产品规范化共享邻居的数的两个社区的大小。索尔顿海分数(65年)也可实现类似的但这一次使用的平方根两节点度的产物。索伦森分数(66年]认为两次共享邻居的计数和规范化的两个邻居的大小。中心推广和中心抑郁分数(67年]规范化共享邻居的数的最小和最大的节点度,分别。优惠附件得分(68年只考虑两个节点度的产物。

全球链接得分比本地方法和预测方法更为复杂。例如,Katz分数(34)和两个节点之间的所有可能路径的影响,增量地惩罚路径的长度根据给定阻尼因子。全球Leicht-Holme-Newman分数(64年Katz)非常类似于分数但度假村的主导特征值来计算最终结果。

随机游走方法模拟随机选择的节点的马尔可夫链(69年]。我们的想法是,从一粒种子节点和随机移动通过链接,我们可以获得一个概率向量中每个元素对应到每个节点的概率。经典随机漫步迭代繁殖概率转移矩阵向量,即row-normalized版本的邻接矩阵,直到收敛。一个有趣的变体是重启的随机漫步(70年),模型回归的可能性种子节点有一个给定的概率。流传播是随机游走的另一个变体(71年),转移矩阵计算通过执行两个邻接矩阵的行和列归一化。

在认识一些光谱技术也可以。光谱技术,当我们提到当讨论社区检测方法,基于拉普拉斯算子矩阵。伪逆拉普拉斯算子的分数(72年)内积的行对应的一对节点的拉普拉斯算子矩阵。另一种光谱技术是平均通勤时间72年],它被定义为步骤,一个随机的平均数沃克从一个特定节点到另一个节点第一次回到初始节点。尽管它模型随机游走过程,它被认为是一种光谱技术,因为它通常是计算拉普拉斯算子的矩阵。鉴于拉普拉斯算子矩阵,它可以计算的对角元素的起始节点+对角元素结束节点,减去两倍的元素位于第一个节点的行和列的第二个。

随机森林内核分数(73年)是一个全球性的技术基于生成树的概念,即。,a connected undirected subnetwork with no cycles that includes all the nodes and some or all the links of the network. The matrix-tree theorem states that the number of spanning trees in the network is equal to any cofactor, which is a determinant obtained by removing the row and column of the given node, of an entry of its Laplacian representation. As a result of this, the inverse of the sum of the identity matrix and the Laplacian matrix gives us a matrix that can be interpreted as a measure of accessibility between pairs of nodes.

使用网络数据挖掘算法在认识很简单。下面的代码片段中,我们展示了如何生成一个Barabasi-Albert优惠附件网络100节点和链接每个节点,然后计算每对节点的资源分配分数使用认识:网络网络= new BarabasiAlbertNetwork (100, 10);LinkPredictionScore方法= new ResourceAllocationScore(网络);矩阵结果= method.call ();

在Python中,前面的示例将实现如下:ns =理智()网络= ns。create_network_from_model(“Barabasi-Albert”, 100, 10)预测= ns.create_link_predictor (“ResourceAlloca-tion”)结果= predictor.compute(网络)ns.end ()

5。性能比较

认识的目的是管理大型复杂网络包括数以千计甚至数以百万计的节点。它提供了结构有效地表示和处理关系数据。而这些特性往往提供的其他网络分析框架,他们往往缺乏认识包括并行计算功能。

在本节中,我们进行实证比较的性能不同的流行的网络分析框架对一些常见的数据分析任务。igraph、吸附和NetworkX框架已被选定为他们比较理智,因为它们提供了一个编程API。软件开发人员可以使用它们作为图书馆在自己的软件项目在相应的软件许可证的限制(几乎没有NetworkX BSD许可证的,,和认识)。封闭源代码的工具,如Pajek,没有提供任何API,而其他工具强烈关注特定领域(例如,Cytoscape交互式网络可视化)。我们限制的比较认识这些工具与用例(即最相似。、igraph吸附和NetworkX)。

认识,不同的CPU调度技术进行了测试:一个工作窃取的调度器(WSS),未来的调度器(FS),调度器(TPS)和传统的线程池。我们的实验进行的英特尔酷睿i7 - 3630 qm处理器(8核在2.40 GHz) 16 GB的RAM Windows下10(64位)。

三个数据集用于我们的实验:一个网络从维基百科中提取27475个节点和85729个链接(可以从下载维基百科的数据集http://spark-public.s3.amazonaws.com/sna/other/wikipedia.gml),一个对等Gnutella文件共享网络从2002年8月6301个节点和20777边缘74年),与4039年Facebook自我网络节点和88234边缘75年]。

本节中的实验进行了包括计算不同计算昂贵的网络指标中常用的网络挖掘:中间性中心(BC),链接中间性(磅),亲密(CN),从每个节点使用迪杰斯特拉最短路径的算法(APSP)。APSP任务不能使用快速实现,因为支持的局限性。我们执行5运行为每个测量和报告完成任务所需的平均执行时间为每个软件工具和网络数据集。

每个任务的平均执行时间/数据/工具三个一组如表所示4。应该注意的是,理智是始终更快,著名的现有框架。性能优越的认识框架可以归因于不同的因素。首先,认识是用纯Java编写的,可数量级的速度比igraph和NetworkX的Python实现。理智的Java代码是高度优化的考虑Java虚拟机的特性(例如,试图减少内存碎片和使用适当的调整成本模型不同的操作)。因此,理智的Java实现惊人的速度比的c++实现,应该会更有效,因为高度优化的c++应用程序通常更有效率比Java同行。认识并行编程设计模式让算法设计人员轻松地利用多核处理器的并行性和多处理器系统。这些特性允许理智的结合完成任务与计算相关重要网络相关结构属性比一些流行的软件包,甚至数量级的速度更快。

在我们的并行化实验,我们实现了不同的CPU调度技术。理智比现有工具无论快调度器采用。认识传统线程池调度程序,实现一个共同的解决方案并行软件的帮助下一个线程池,持续获得最好的结果批实验我们已经进行。另一个实现使用Java特性会稍微慢一些。类似的结果使用工作窃取CPU调度程序(76年]。在工作窃取调度程序中,每个处理器的计算机系统有一个队列工作项(计算任务(线程)来执行。当一个处理器运行的工作,它着眼于其他处理器的队列,“窃取”他们的工作项。因此,工作窃取分发调度工作空闲处理器,只要所有的处理器有工作要做,没有发生调度开销。Cilk是受雇于调度程序的编程语言(77年),Java fork / join框架(78年,. net任务并行库(79年]。我们执行的测试,其中包括一个多核处理器的沉重的工作负担,最简单的策略似乎效果更好,但典型的工作负载可能是不同的,选择CPU调度程序可能是更可取的。

6。结论

在本文中,我们提出了复杂网络数据挖掘的认识框架。认识为网络提供了大量的数据分析技术,在一个比竞争对手更有效的方式选择,自从认识利用现有硬件的并行使用结构化的并行编程设计模式(80年]。如图所示在我们的实验中,认识明显比其他库,甚至数量级的速度,这是非常重要的在处理大规模网络。

目前,认识项目取得了成熟的地位超过三万五千行Java代码中,数以百计的类,和几十个包。此外,生产代码覆盖的自动化单元测试,以确保实现算法的正确性。理智的可重用组件包括一个自定义库超过四万行,提供不同的功能,如可定制的集合,结构化并行编程构建块,数学例程,和一个模型驱动的应用程序生成器的认识图形用户界面。由于Python已经成为科学计算的一个非常流行的编程语言,一个完整的API提供了Python绑定,以便认识可以从Python使用。

理智是最完整和有效的“开箱即用”的框架分析和挖掘关系数据。我们的框架可以加快发展软件需要分析网络通过提供高效和可伸缩的数据挖掘技术,覆盖网络的不同方面。我们的框架是开源和免费从其官方网站,http://noesis.ikor.org宽容的Berkeley Software Distribution许可协议。

数据可用性

网络数据集用于我们的绩效评估是公开的研究中,在我们的论文中被引用。网络数据集可以从斯坦福大学获得大型网络数据集收集(http://snap.stanford.edu/data)。

信息披露

认识框架一直是数据挖掘技术的发展的基础组成戈麦斯的博士论文81年]。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

认识项目部分支持的西班牙经济和欧洲区域发展基金(菲德尔),在格兰特tin2012 - 36951,和西班牙教育部根据该计划”效果对位contratos博士前的帕拉formacion德医生2013”(格兰特博士前的bes - 2013 - 064699)。作者感谢亚伦玫瑰花,Francisco-Javier希洪,Julio-Omar -帕拉西奥市,他们的贡献在认识社区检测方法的实现。

引用

1. P.-N。施泰因巴赫,m .,诉Kumar et al .,数据挖掘导论皮尔森,艾迪生韦斯利,波士顿,MA,美国,2006年。
2. s Boccaletti诉Latora y莫雷诺,m·查韦斯和d .黄”:复杂网络的结构和动力学,物理的报告,卷424,不。4 - 5,175 - 308年,2006页。视图:出版商的网站|谷歌学术搜索
3. r . Tamassia手册的图形和可视化美国佛罗里达州波卡拉顿,CRC新闻,2013年。
4. a . Lancichinetti和美国走,”社区检测算法:比较分析”,物理评论E,卷80,不。5,2009。视图:出版商的网站|谷歌学术搜索
5. l . Getoor和c·p·迪”链接挖掘。”ACM SIGKDD探索通讯,7卷,不。2、3 - 12,2005页。视图:出版商的网站|谷歌学术搜索
6. l . Lu和t .周”,在复杂网络链路预测:一项调查,”自然史答:统计力学及其应用,卷390,不。6,1150 - 1170年,2011页。视图:出版商的网站|谷歌学术搜索
7. 诉马丁内斯、c·卡诺和a·布兰科”ProphNet:一般优先级方法通过传播的信息,“BMC生物信息学,15卷,不。S1, 2014年。视图:出版商的网站|谷歌学术搜索
8. m .巴甫洛夫和r . Ichise找到链接预测专家的共同创作的网络,”寻找专家与语义Web研讨会卷。290年,42-55,2007页。视图:谷歌学术搜索
9. l .页面,美国布林、r . Motwani和w·特里“PageRank引文排序:将以网络,“技术代表、斯坦福InfoLab斯坦福,CA,美国,1999年,技术报告。视图:谷歌学术搜索
10. j . Ellson e . Gansner l . Koutsofios s . c .北和w·戈登,“Graphviz-open源图绘图工具,”图绘制施普林格,页483 - 484年,2002年柏林,琦玉。视图:谷歌学术搜索
11. 欧文·香农a . Markiel o . et al .,“Cytoscape:生物分子相互作用网络的集成模型的软件环境,”基因组研究,13卷,不。11日,第2504 - 2498页,2003年。视图:出版商的网站|谷歌学术搜索
12. g . Csardi和t . Nepusz igraph软件包为复杂网络研究”,InterJournal,复杂的系统,卷1695,不。5,页1 - 9,2006。视图:谷歌学术搜索
13. d . a . Schult p .黑黝黝的,“探索网络结构、动力学和功能使用networkX”第七届Python学报》在科学会议(2008年SciPy)11 - 16页,卷。2008年,帕萨迪纳市,美国,2008年8月。视图:谷歌学术搜索
14. Leskovec和r . Sosič“提前”,ACM智能交易系统和技术,8卷,不。1,1,2016页。视图:出版商的网站|谷歌学术搜索
15. 诉Batagelj和a . Mrvar Pajek-program对于大型网络分析,“连接,21卷,不。2,47-57,1998页。视图:谷歌学术搜索
16. m·a·史密斯,美国本:Milic-Frayling et al .,“与NodeXL分析(社交媒体)网络,”学报》第四国际会议对社区和技术大学,页255 - 264,ACM公园,PA,美国,2009年6月。视图:谷歌学术搜索
17. m·巴斯蒂安·s·海曼,m . Jacomy et al .,“Gephi:探索和操纵网络的开放源码软件,”博客和社交媒体上国际AAAI会议,8卷,第362 - 361页,2009年。视图:谷歌学术搜索
18. s . p . Borgatti m·g·埃弗雷特,l·c·弗里曼”UCINET对windows:社会网络分析软件,“技术代表、技术报告、分析技术,列克星敦肯塔基州,美国,2002年。视图:谷歌学术搜索
19. j·迪恩和s .格玛沃特”MapReduce,“ACM的通信,51卷,不。1,第113 - 107页,2008。视图:出版商的网站|谷歌学术搜索
20. Leskovec和a . Krevl临时数据集:斯坦福大学大型网络数据集收集美国斯坦福大学,斯坦福大学,2014年,http://snap.stanford.edu/data。
21. m·e·j·纽曼,网络:介绍英国牛津,牛津大学出版社,2010年。
22. m·o·杰克逊,社会和经济网络美国新泽西州普林斯顿大学,普林斯顿大学出版社,2008年。
23. p . Erdős和a . Renyi随机图。”出版Mathematicae德布勒森》第六卷,第297 - 290页,1959年。视图:谷歌学术搜索
24. e·n·吉尔伯特,“随机图”,数理统计年鉴中,30卷,不。4、1141 - 1144年,1959页。视图:出版商的网站|谷歌学术搜索
25. d·j·瓦和s . h .““集体动力学的“小世界”网络”,自然,卷393,不。6684年,第442 - 440页,1998年。视图:出版商的网站|谷歌学术搜索
26. r·艾伯特和A.-L。巴斯”统计力学的复杂网络,“现代物理学的评论,卷74,不。1,47 - 97、2002页。视图:出版商的网站|谷歌学术搜索
27. m·e·j·纽曼,“复杂网络的结构和功能,暹罗审查,45卷,不。2、167 - 256年,2003页。视图:出版商的网站|谷歌学术搜索
28. m . Piraveenan m . Prokopenko, a . y . Zomaya“当地assortativeness在无标度网络,”EPL (Europhysics字母),卷84,不。2、文章ID 28002, 2008。视图:出版商的网站|谷歌学术搜索
29. m . Piraveenan m . Prokopenko y艾伯特,Zomaya,“使用无偏当地assortativity分类复杂网络,”第十二学报》国际会议上生活的综合和仿真系统欧登塞,页329 - 336年,丹麦,2010年8月。视图:谷歌学术搜索
30. p . Hage和f . Harary偏心度和中心的网络,”社交网络,17卷,不。1,57 - 63,1995页。视图:出版商的网站|谷歌学术搜索
31. a . Bavelas“通信模式在面向任务的群体,”《美国声学学会杂志》上,22卷,不。6,725 - 730年,1950页。视图:出版商的网站|谷歌学术搜索
32. l·c·弗里曼,“一套措施基于中间性的中心,“人与人之间,40卷,不。1,35-41,1977页。视图:出版商的网站|谷歌学术搜索
33. j . m . jonkleinberg“权威来源在超链的环境中,”ACM的杂志,46卷,不。5,604 - 632年,1999页。视图:出版商的网站|谷歌学术搜索
34. l . Katz,“一个新的地位指数来源于社会经济的分析,“心理测量学,18卷,不。1,39-43,1953页。视图:出版商的网站|谷歌学术搜索
35. 康,c·莫里纳罗克劳斯,y Shavitt, v . s . Subrahmanian,“社交网络扩散中心,”《2012年国际会议上的进步社会网络分析和挖掘(ASONAM 2012),页558 - 564,IEEE计算机协会,土耳其伊斯坦布尔,2012年8月。视图:谷歌学术搜索
36. m . Piraveenan m . Prokopenko, l·侯赛因”渗透中心:量化节点在网络渗透,用图的影响”《公共科学图书馆•综合》,8卷,不。1,文章ID e53095, 2013。视图:出版商的网站|谷歌学术搜索
37. m . r . Faghani和美国t .阮XSS蠕虫传播的研究和检测机制在在线社交网络,”IEEE取证和安全信息,8卷,不。11日,第1826 - 1815页,2013年。视图:出版商的网站|谷歌学术搜索
38. m . Piraveenan g . Thedchanamoorthy s Uddin和k . s . k .钟”量化网络拓扑鲁棒性持续的有针对性的袭击下,“社会网络分析和挖掘,3卷,不。4、939 - 952年,2013页。视图:出版商的网站|谷歌学术搜索
39. t . m . j . Fruchterman和e . m . Reingold“图形绘制到指定位置,”软件:实践和经验,21卷,不。11日,第1164 - 1129页,1991年。视图:出版商的网站|谷歌学术搜索
40. t . Kamada和s·卡瓦依图纸一般无向图的算法”,信息处理信件没有,卷。31日。1、7 - 15,1989页。视图:出版商的网站|谷歌学术搜索
41. d . Lusseau k .施耐德o . j . Boisseau p•哈斯e . Slooten和s·m·道森”怀疑声音特征的宽吻海豚社区大部分持久的关联,”行为生态学和社会生物学,54卷,不。4、396 - 405年,2003页。视图:出版商的网站|谷歌学术搜索
42. g . j .遗嘱“NicheWorks:交互式的可视化非常大的图表,“计算和图形统计杂志》上,8卷,不。2、190 - 212年,1999页。视图:出版商的网站|谷歌学术搜索
43. d . Liben-Nowell和j . jonkleinberg”link-prediction社交网络的问题,“《美国社会信息科学和技术,卷。58岁的没有。7,1019 - 1031年,2007页。视图:出版商的网站|谷歌学术搜索
44. w·w·扎卡里,”一个信息流模型在小群体冲突和分裂,”《人类学研究,33卷,不。4、452 - 473年,1977页。视图:出版商的网站|谷歌学术搜索
45. 事务部门主管r . Sibson“早产:单键群的最佳有效的算法方法,”电脑杂志,16卷,不。1 - 34,1973页。视图:出版商的网站|谷歌学术搜索
46. d . Defays”,一个高效的算法对于一个完整的链接方法,”电脑杂志,20卷,不。4、364 - 366年,1977页。视图:出版商的网站|谷歌学术搜索
47. b .刘Web数据挖掘施普林格,柏林,德国,2版,2011。
48. m·e·j·纽曼,“快速检测在网络社区结构的算法,”物理评论E,卷69,不。6、2004。视图:出版商的网站|谷歌学术搜索
49. p . Schuetz和a . Caflisch”有效的模块化多步优化的贪婪算法和顶点发细化,”物理评论E,卷77,不。4、2008。视图:出版商的网站|谷歌学术搜索
50. b·w·克尼汉和美国林”,一个有效的启发式程序分区图,“贝尔系统技术杂志卷,49号2、291 - 307年,1970页。视图:出版商的网站|谷歌学术搜索
51. j . MacQueen“一些分类方法和多变量分析观察,”《第五伯克利研讨会上数理统计和概率,页281 - 297,奥克兰,美国1967年1月。视图:谷歌学术搜索
52. l·哈根和a . b . Kahng“新光谱比率减少分区和聚类的方法,”IEEE计算机辅助设计的集成电路和系统,11卷,不。9日,第1085 - 1074页,1992年。视图:出版商的网站|谷歌学术搜索
53. a . y . Ng,约旦,y . Weiss et al .,“光谱聚类:分析和算法”,先进的神经信息处理系统,2卷,第856 - 849页,2002年。视图:谷歌学术搜索
54. j .简帛史和j·马利克、“规范化的削减和图像分割,”IEEE模式分析与机器智能,22卷,不。8,888 - 905年,2000页。视图:出版商的网站|谷歌学术搜索
55. j·杨和j . Leskovec“重叠社区发现规模:一个非负矩阵分解方法,”学报第六届ACM国际会议网络搜索和数据挖掘ACM,页587 - 596年,罗马,意大利,2013年2月。视图:谷歌学术搜索
56. 走,“社区检测图”,物理的报告,卷486,不。3 - 5,75 - 174年,2010页。视图:出版商的网站|谷歌学术搜索
57. m·e·j·纽曼和m . Girvan“发现和评估网络社区结构,”物理评论E,卷69,不。2、2004。视图:出版商的网站|谷歌学术搜索
58. d . e . Knuth和s . GraphBase一个组合计算的平台美国,addison - wesley,波士顿,MA,第1版,2009年版。
59. m·e·j·纽曼,“集群和优先连接在日益增长的网络。”物理评论E,卷64,不。2、2001。视图:出版商的网站|谷歌学术搜索
60. 达洛杉矶亚当和大肠”,在网络上的朋友和邻居,”社交网络,25卷,不。3、211 - 230年,2003页。视图:出版商的网站|谷歌学术搜索
61. 周t、l . Lu和研究。张“预测失踪链接通过当地信息,”欧洲物理期刊B,卷71,不。4、623 - 630年,2009页。视图:出版商的网站|谷歌学术搜索
62. 诉马丁内斯,f . Berzal J.-C。Cubero”链接预测自适应程度处罚。”计算机科学期刊,13卷,不。2016年1 - 9。视图:出版商的网站|谷歌学术搜索
63. j·保罗,“练习曲比较de la分布花香des阿尔卑斯et des侏罗山脉中一个部分,“公报de la法国Vaudoise des科学只是37卷,第579 - 547页,1901年。视图:谷歌学术搜索
64. e . a•莱克特说,p .河中沙洲,m·e·j·纽曼“顶点相似性网络”物理评论E,卷73,不。2、2006。视图:出版商的网站|谷歌学术搜索
65. g·索尔顿海和m . j .麦吉尔,现代信息检索概论,麦格劳-希尔公司,纽约,纽约,美国,1986年。
66. t . Sørensen”,等于振幅的方法建立组植物社会学基于相似的物种及其应用分析植被的丹麦,“Biologiske Skrifter5卷,猴,1948页。视图:谷歌学术搜索
67. e . Ravasz a . l . Somera d . a . Mongru z n . Oltvai A.-L。巴斯”层次模块化组织的代谢网络,科学,卷297,不。5586年,第1555 - 1551页,2002年。视图:出版商的网站|谷歌学术搜索
68. A.-L。巴巴斯和r·阿尔伯特”出现随机网络的扩展,“科学,卷286,不。5439年,第512 - 509页,1999年。视图:出版商的网站|谷歌学术搜索
69. k·皮尔森,“随机漫步的问题。”自然,卷72,不。1867,342年,页1905。视图:出版商的网站|谷歌学术搜索
70. h, c·凯利,J.-Y。锅”,与重启及其应用,快速随机游走”数据挖掘学报第六届国际会议上ICDM 06年,页613 - 622,IEEE计算机协会,香港,中国,2006年12月。视图:谷歌学术搜索
71. o·瓦努努和r . Sharan propagation-based算法推断基因-疾病伴侣”德国生物信息学大会学报》上页,54-52德累斯顿,德国,2008年9月。视图:谷歌学术搜索
72. f .入手,a . Pirotte人类。呈现,m . Saerens“随机游走图的计算节点之间的相似性与协作应用程序的建议,“IEEE工程知识和数据,19卷,不。3、355 - 369年,2007页。视图:出版商的网站|谷歌学术搜索
73. p . Chebotarev和e•沙弥”Matrix-forest定理”,2006年,https://arxiv.org/abs/math/0602575。视图:谷歌学术搜索
74. m . Ripeanu。福斯特,a . Iamnitchi”映射使用gnutella网络:大规模p2p系统的性质和影响系统设计,”2002年,https://arxiv.org/ftp/cs/papers/0209/0209028.pdf。视图:谷歌学术搜索
75. Leskovec和j。j Mcauley”,学习发现在自我网络社交圈子”诉讼进展的神经信息处理系统太浩湖,页539 - 547年,NV,美国,2012年12月。视图:谷歌学术搜索
76. r·d·Blumofe和c . e .雷瑟尔森”调度多线程计算工作窃取。”ACM的杂志,46卷,不。5,720 - 748年,1999页。视图:出版商的网站|谷歌学术搜索
77. r·d·Blumofe c . f . Joerg公元前Kuszmaul, c, e .雷瑟尔森k·h·兰德尔和y周,“Cilk:一个高效的多线程运行时系统,”杂志的并行和分布式计算,37卷,不。1,55 - 69、1996页。视图:出版商的网站|谷歌学术搜索
78. d . Lea“Java fork / join框架,”Java Grande ACM学报2000年会议第36页。ACM,旧金山,CA,美国,2000年6月。视图:谷歌学术搜索
79. d . Leijen w·舒尔特,s . Burckhardt”任务并行库的设计。”ACM SIGPLAN通知,44卷,不。10日,227 - 242年,2009页。视图:出版商的网站|谷歌学术搜索
80. m·d·迈克尔,公元罗宾逊,j . Reinders结构化的并行编程:模式有效的计算爱思唯尔,荷兰阿姆斯特丹,2012年。
81. 诉m·戈麦斯”监督数据挖掘在网络:链接预测和应用程序,”格拉纳达大学,格拉纳达,西班牙,2018年博士论文。视图:谷歌学术搜索

版权

版权©2019维克多马丁内斯等。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。