英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
摘要
在本文中，我们对互联网电影数据库（IMDB）派生的大型复杂时态多变量网络进行了可视化分析和研究。通过将网络分析方法与可视化相结合，达到解决可扩展性和复杂性问题的目的。我们定义了新的分析方法，如（p，q） - 核和4环，从巨大的二分图中识别重要的密集子图和短周期；为了识别重要且有意义的子图，我们对特定时间片应用岛分析；此外，提取Kevin Bacon图和时间双模网络，进而推测关于电影行业发展的结论。
关键词：大型复杂网络，案例研究，可视化，网络分析，IMDB。
1简介
随着技术的发展，许多领域产生了大量的数据，并且构成了大型和复杂的网络模型。这其中包括：
- Webgraphs：实体是网页，关系是超链接，数据量巨大：整个数据库包含数十亿个节点。
- 社交网络：包括电话呼叫图（用于追踪恐怖分子），货币流动网络（用于检测洗钱），引文网络或协作网，网的规模有大有小。
- 生物网络：生物学家使用蛋白质-蛋白质相互作用（PPI）网络，代谢途径，基因调控网络和系统发育网络来分析和设计生化材料。虽然它们通常较小，只有数千个节点，但是这些网络中的关系却非常复杂。
了解这些网络是分析许多应用程序的关键，而分析这些网络又需要用到已有的可行的分析方法。另外要考虑大众的接受能力，否则分析就没有了实际意义，因此可视化成为理解此类网络的有效工具。良好的视觉化揭示了网络的结构，增强了读者的理解，从而为未来带来了新的理解，新的发现和可能的预测。
在大型复杂网络的分析和可视化中，我们主要是解决以下几个问题：
- 可扩展性：AT＆T收集的Web图或电话呼叫图有数十亿个节点。有时无法将整个图形可视化，或者无法将整个图形加载到主存储器中，因此对于从数据库到计算机图形学的研究，新的分析和可视化方法的设计很有必要。
- 复杂性：例如，社交网络中的参与者之间的关系可以具有多种属性（观察到的行为可以被证实或不被证实，关系可以被定向或不定向，并且可以通过概率加权），生物网络本质上相当复杂；又例如，代谢途径只有几千个节点，但它们之间的关系和相互作用非常复杂。数据可能是天生的，但数据的某些部分可能是人类科学家所不知道的。解决这些复杂性问题的分析和可视化方法的设计是第二个研究挑战。
- 网络动态性：真实世界的网络总是在不断变化。许多社交网络网图，在逐渐过时的情况下逐渐消失；电话呼叫网络的数据图则是一个非常快速流动的图。 对动态网络进行有效和高效的建模也是分析和可视化研究中非常具有挑战性的研究课题之一。
为了解决这些具有挑战性的问题，我们将分析与可视化和交互相结合。如果没有可视化，网络分析工具就无法很好的呈现结果，如果可视化不与分析相关联，那么可视化工具也不能发挥作用。另外，我们需要进行交互以便从可视化中得出更多结论与启发。
在本文中，我们通过获取IMDB的数据呈现一个关于大型复杂多变量网络整合分析，可视化和交互的案例。IMDB是一个庞大且丰富的具有许多属性的数据集，它已经成为一个可视化研究人员具有挑战性的数据集。
在可视化小世界网络的多尺度方法中，有人提出了一种动态融合网络的可视化方法，将事件由一组描述符表征，设计了一个径向波纹隐喻来显示时间的流逝，并通过适当的布局传达不同成分之间的关系。但值得注意的是，该方法适用于以自我为中心的观点。
我们方法的第一步是将网络分析方法与可视化相结合。我们定义了新的分析方法，如（p，q） - 核和4环，以从巨大的二分图中识别出重要的密集子图和短周期。我们对特定时间片应用岛屿分析，以便找出大型复杂网络的重要且有意义的子图。此外，提取并可视化时间Kevin Bacon图和时间双模网络，以便提供关于IMDB数据集的演变的见解和知识。。
论文结构如下。在第二节中，我们将对IMDB数据集进行简单分析。在第3节中，我们介绍了网络分析方法与大型二分图可视化的集成，包括（p，q） - 核，4环和岛。第4节介绍了基于Kevin-Bacon数字的视觉分析。第5节介绍了时间两种模式演员-电影网络的角色监视，以及对具有公司属性的两种模式网络的可视化分析。第6节总结。
2 IMDB的基本特征
原始数据的来源是因特网电影数据库。我们将比赛数据转换为时间网络，其中一些额外的向量和分区描述了顶点的属性。IMDB网络是二分式（两种模式），具有1324748 = 428440 896308个顶点和3792390个弧。网络中的9927个弧是多个（并行）弧。(图略)
3大型双极网络的可视化和分析
很少有专门的方法来分析二分网络，特别是大型网络。由于IMDB网络的大小，整个网络到一个或另一个派生的单模网络的标准减少不是一种选择。这促使我们设计和实施两种分析二分网络的新方法：
- 双核版本的核心 -（p，q）- 核心
- 线路上的4环权重
3.1（p，q） - 核心分析
双模（双模式）网络N =（V1，V2; L），子集变换Csube;V是一个（p，q）- 核，V =V1cup;V2如果有且只有
- 在诱导子网中K =（C1，C2; L（C）），C1 =Ccap;V1，C2 =Ccap;V2它保持forall;visin;C1：deg K（v）ge;p;
- 且forall;visin;C2：deg K （v）ge;q；C是满足条件的V的最大子集。
二分核的基本属性是：
-
-
- C（0,0）= V
- K（p，q）并不总是连接
- （p1le;p2）and;（q1le;q2）rArr;C（p1，q1）sube;C（p2，q2）
-
使用（p，q） - 核心，我们可以识别大型复杂网络的重要缺陷结构。我们设计了一个非常有效的O（m）算法来完成（p，q） - 核心，并在Pajek中实现。
由于有许多（p，q） - 核心，为了帮助用户进行这些决定，我们实现了一个主要特征n1 = | C1（p，q）|，n2 = | C2（p，q）|和k - K（p，q）中的组分数。我们寻找（p，q） - 核，其中
- n1 n2le;选择的阈值
- 从C（p-1，q）和C（p，q-1）到C（p，q）的大跳跃。
3.2 4环分析
K环是长度为k的简单闭链。使用k形环，我们可以将边的权重定义为包含边eisin;E的k形环的wk(e)=#。
因为对于完整的图Kr，rge;kge;3，我们得到（Kr）=（r-2）！/（r-k）！属于派系的边具有大的权重。 因此，这些权重可用于识别网络的密集部分。 例如，选出网络的所有属于权重w3的r-2边组成r-集
3环重量已经可用。但是，IMDB网络中没有3环。最密集的子结构是完整的二分子图Kp，q。它们包含许多4环。因此我们设计一种找到4环重量的方法并在Pajek中实现它。为了识别有意义的子结构，我们对权重w4应用了简单的岛程序。在1400 MHz，1GB RAM计算机上计算w4权重需要大约三分钟，在确定岛屿时需要13秒。我们在56086个顶点上获得了12465个简单的线状岛，每个岛屿代表一个特殊主题。
3.3时间片和岛分析
通过从完整网络中提取时间片，我们可以识别所选时间段内的主要组。群岛可以根据属性的值来识别大型网络的重要子图。例如我们提取了时间片1935-1950，在1774个顶点上有223个简单岛用于w4。我们选择了6岛 - #39;Dona Macabra#39;; 见下图。
4共同主演网络：KEVIN-BACON网络
我们在IMDB网络中选择了一小部分演员，并从中构建了一个1-模式网络的动态可视化来演示演员在电影中的共同主演情况。
为了定义一个足够小的重要子图，我们首先只考虑网络中Kevin Bacon数为1的节点。演员的Kevin Bacon数与数学家的埃尔多数相似; 它代表了从演员到凯文·培根的电影明星合作网络中最短路径的长度。数据集被分为长度为十年的时间片（例如20世纪20年代，20世纪30年代等），并且每个十年中演员的集合减少到仅与其他演员共同演出至少5部电影的Kevin Bacon数为1的演员。
这些简化的演员集合的单模共同主演网络是以十年为间隔构建的，并且使用GEOMI 中的无标度网络布局为每个演员生成三维布局。布局中的节点被限制在三个同心球体中的一个上，每个节点的着色也用于表示程度，每个节点的大小表示演员在该特定十年中出演的电影数量，边的宽度用于表示十年内两个演员之间共同出现的次数。
为了有效地说明共同主演网络的演变，我们将后续几十年的布局做成流畅的动画。动画分成几个部分，一个接一个地显示出来，以帮助保留心理地图。首先，第一种布局中不存在的节点和边缘逐渐消失，在第一和第二布局中呈现的节点被移动到第二布局中的新位置，第二个布局的新节点从中心突然出现并停留在计算位置，之后新边缘逐渐出现，以显示第二个十年的新合作。该动画可从http://www.it.usyd.edu.au/~dmerrick/gd05contest/gd05 fi nal.avi下载。
从1911年到2004年，这个过程持续了所有十年的切片，结果可以在可下载的动画中看到。
可视化显示了许多有趣的事实，一个意想不到的发现是在二十世纪初期Kevin Bacon数为1的大量演员中，其中一些显然没有与Kevin Bacon共同出演电影。这揭示了电影数据集的收集中的一些问题，说明一些电影的年代被错误地录制，而与其电影同名的电影的边则被记录在该电影中。
在20世纪60年代，视觉分析揭示了美国总统John F. Kennedy的影响。这是由于Kennedy于1963年被暗杀，以及随后发生的关于这次事件的大量报道。在集团（Jacqueline Kennedy，John和Nellie Connally等）的所有人都出现在暗杀事件中。他们出现在这个数据集中是因为由Kevin Bacon主演的电影JFK包括暗杀的真实存档镜头。可视化的后几十年也展示了基于此事件拍摄的大量纪录片。
20世纪70年代，好莱坞演员的第一大联盟群体出现，它们至今仍然是大牌。 James Earl Jones，Robert Redford，Steve Martin和John Travolta都出现在这个小组中。
20世纪80年代的可视化则突出了一些特别紧密的演员群体。喜剧明星Chevy Chase，Dan Akroyd和Bill Murray出现在Satuday Night Live，Caddy Shack和Spies Like Us中。同时出席的还有Jim Cummings,，Jack Angel 和 Rob Paulson,，他们在很长时间内都有很高的成绩，并且在短片和剧集中都有很好的表现。
这些组继续到20世纪90年代，其中组的反应器变得更大并且连接更高。像Whoopi Goldberg，Tom Hanks和Dennis Hopper这样的现代演员在这十年中变得尤为突出。
最后，在2000年代，我们看到了一些特别有趣和意想不到的现象。首先，像Britney Spears, Beyoncacute;e Knowles和Sheryl Crow这样的音乐明星由于参加了许多音乐颁奖典礼出现了非常高的相关程度和相互关联性。另外，受欢迎的演员阿诺德施瓦辛格将政治家与其他联合主演网络中的电影明星和音乐家联系起来，。这主要是因为Schwarzenegger进入政界，成为美国加利福尼亚州的州长。之后，他出现在几部政治纪录片中，而Bill Clintonal也出现了。Bill Clinton又通过文献和档案录像链接到其他着名的政治家，如Ronald Reagan, Richard Nixon 和John F. Kennedy。
5 演员电影网络的电影明星星系
本节描述了具有动画的时间演员电影网络的电影明星系列（为了查看概述），以及特定时间片网络的可视化（以便查看详细信息）。
首先，我们考虑一个电影演员网络的“星系”隐喻。主要思想是将“电影明星”映射到显示演员-电影互动的星系的电影（即动画）中。
在可视化大型数据集时，尽可能多地表示信息而不引入压倒性的视觉复杂性一直是一个挑战。我们定义了重要的子图来降低视觉复杂度，如下所示。
我们将IMDB中的“明星”定义如下：
- 每个明星演员必须在整个时间段内播放超过12部电影
- 每部明星电影必须有超过12位演员
- 每位明星演员必须在三节之间播放每年六部电影
我们再次使用二分（2模式）网络模型。有两种类型的节点：演员节点和电影节点。演员节点在夜空中显示为星星，边缘显示为连接演员“星座”的微弱线条。在演员和电影节点之间显示带弯曲的边缘；隐藏电影节点，可以很容易地看到演员之间的合作。 在这种情况下，图片不仅降低了视觉复杂性（特别是对于边缘），而且还同时表示演员-电影和演员-演员的交互。
为了进行时间网络动态的概述，我们计算了从1907年到2004年的每年的布局并制作了动画。使用GEOMI 为每年的子图生成了二维力导向布局。以与上一部分中共同主演作者网络的动画类似的方式在每个布局之间生成动画。动画可从http://www.it.usyd.edu.au/~dmerrick/gd05contest/gd05- fi nal.avi获得。
一旦我们使用动画表示了时间网络，我们现在关注的是网络的特定年份，在特定的时间段内观察一些有趣的现象。
左图显示了1918年布局的一部分。这三个演员共同出演了一部分电影;另一方面，它们并没有出
全文共7153字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[2984]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
