阿萨斯大学经济管理信息与传播学院的2019年10月论文研究：图中聚类的动态近似：度量和应用

阿萨斯大学-阿萨斯经济、管理、信息与传播学院2019年 10月24日，Docto在INFormatique的Tese持续图中聚类的动态近似：度量和应用。纪尧姆·维蒙特在Michel DE Rougemont报告员：M. 克里斯托弗神父，教授M. SALAMATianKaVe，教授aPOlytech安纳西-查姆贝里评审团成员：夫人。在第五届大会上，我将在第一届大会上发言。M. SPYRATOSNicolas，南方大学ESSEUReMEERITE教授2019年10月20日星期五VIMONTGUILLaume-T'hesededoctorat-2019年10月- 3128-警告：因此，联合国倾向于对本文中表达的观点给予认可和不认可;这些观点必须被认为是其作者所特有的。VimontGuillaume-T'hesededoctorat-2019年10月4128-VIMONTGUILLaume-T'hesededoctorat-2019年10月- 5128-谢谢你我想感谢并表达我的感 激 之 情 ，我的 T'Hese主任，教授Mi CHeldeROUGEMONT谁使这一travailp成为可能。 他的建议，生活和建议，你不是无价的所有'etapes的travail。我还要感谢我的L'Egues上校，我的朋友们，在实现这一目标的过程中，他们对我的所有支持。最后，我要感谢我的家人所有的爱和鼓励。我的父母在我所有的活动中都不支持我，我的朋友也支持我，鼓励我，支持我，在这个过程中。我感谢你。纪尧姆·维蒙大学诉替代品Pantheon-阿萨斯2019年6月VimontGuillaume-T'hesededoctorat-2019年10月6128-VIMONTGUILLaume-T'hesededoctorat-2019年10月- 7128-√√ √我是：我们研究的是如何在一个由一个集合的fl ux定义的graphe中构造聚类，而不考虑图的意义。我们不像不像不切大团簇的顺序 n在Ontm=O（nlog（n））为r的群中，而stockant n.G（n）为R。 S或C图不遵循满足该条件的方案。将我们的应用程序扩展到动态定义图形，使用最新的图形和有很多人。我们提供简单、坚固的产品，以满足这些需求。男人的集群我是aprochee.我们用两个flxρ（t）在时间t的fen中的群rs的Jaccardt'e相似性来定义它们的cornten的关系。我们提出了一个简单而有效的方法来应用我们的在线关系和MOntron，因为对于遵循幂律的动态随机图，我们可以保证一个很好的近似。其中一个应用程序是 我们在网上计算这些FL的CONTE N关系。然后，我们将把它们放在一个地方，在那里我们将把它们放在一个地方。因此，它们不是由关系的核心来排序的，它们的解释也不是由集群来处理的。描述符：流算法，动态图，聚类，近似VimontGuillaume-T'hesededoctorat-2019年10月8128-√√摘要：我们研究了如何在由边流定义的图中检测聚类，而不使整个图环化。我们展示了如何在存储n的同时，在具有m = O（n log（n））边的图中检测n阶的大聚类。对数（n）边。社交图满足此条件（M）。我们将我们的方法扩展到由最近的边流和多个流定义的动态图。我们提出了一种简单而稳健的基于近似的方法来检测这些聚类。我们将两个流的内容相关性定义为ρ（t）是它们在时间t之前的窗口中的聚类的Jaccard相似性。我们提出了一种简单有效的方法来近似这种在线相关性，并表明对于遵循幂律的动态随机图，我们可以保证一个良好的近似。作为一个应用程序，我们跟踪Twitter流，并在线计算它们的内容相关性。然后，我们提出了一种相关性搜索，其中对关键字集的回答完全基于流的小相关性。 答案按相关性排序，解释可以用存储的聚类来跟踪。关键词：流算法、动态图、聚类、近似VIMONTGUILLaume-T'hesededoctorat-2019年10月- 9128-总结感谢5导言13背景15捐款16Th'ese18.....................................................................................................................................1图形和电子表格191.1图的理论19......................................................................................................................1.1.1定义19..................................................................................................................1.1.220度的分布..........................................................................................................1.1.3第21章第一次见面...............................................................................................1.1.3.1G-raphe有统一的饮食22.......................................................................1.1.3.2埃尔德奥斯-雷恩伊22..............................................................................1.1.3.3配置离子22的元素................................................................................1.1.3.4Mod'ele................................................................................................1.1.424号公路.............................................................................................................1.2Milgram26.......................................................................................................................1.3集群261.3.1密集Te27..............................................................................................................1.3.2电导28..................................................................................................................1.4聚类系数291.5距离和如果milarite31.......................................................................................................2 Twitter上的评论332.1收到的礼物数量为34..........................................................................................................2.1.1Twitter搜索API352.1.2Twitter流媒体API36VimontGuillaume-T'hesededoctorat-2019年10月10128-2.2 Twitter上的捐款数量39...................................................................................................2.2.1结构392.2.2 内容392.3 从JSON树构建................................................................................................................2.3.1Mod'eleNaoyunGephi41.....................................................................................2.3.2 唐44岁时的TWitter图......................................................................................2.4 我是Twitter上的一个.............................................................................................................2.4.1第47章第一次见面................................................................................................2.4.2 我是谁和这ntralite48...........................................................................................2.4.3 路径的平均距离503图513.1第52章第一次见面...........................................................................................................3.1.1C.光泽52..............................................................................................................3.1.2"spatiali es"g中缝上的k-平均值...........................................................................3.2 技术55师3.2.1吉尔万和纽曼553.2.2 Kernighan-Lin启发式573.3 光谱技术573.3.1频谱划分573.3.2 我的超次元帝国58...............................................................................................4 静态S/C图中聚类的近似或4.1Echanti lllonnagea............................................................................................................4.1.1Echantillonnage由Reservoir63...................................................................................4.1.2ECHANTillonnageBiaiSe65..................................................................................4.2 我的超次元帝国65............................................................................................................4.3 图中聚类集合的Methodes66.............................................................................................4.3.1允许大γ-簇66的图4.3.2 在eatoires 68的一个图形网络中的聚类集合..........................................................4.3.2.1统一案例684.3.2.2S浓度694.4 聚类的近似值714.5 对该领域的5在动态S-O5.1Echantillonnage从.............................................................................................................5.1.1E..........................................................................................................................VIMONTGUILLaume-T'hesededoctorat-2019年10月- 11128-5.1.2步骤罐取样785.2 动态图中的聚类集合的数学80...........................................................................................5.2.1具有大簇805.2.2 Graphes在一个rétes81的flux中有动态的随机性.................................................5.2.2.1均匀动力学825.2.2.2动力学概念82.......................................................................................5.2.2.3动力学83..............................................................................................5.2.3 C组中的圣阿比利Te84.........................................................................................5.3 其他方法855.4 对该领域的6 我不想浪费时间876.1我从..................................................................................................................................6.1.1我不想从flux twitter89毕业................................................................................6.2 结的关系和其他ferentsflux90................................................................................................6.2.1PhYloGenie94......................................................................................................6.3 Rec herchebas'e引擎在图形的flux的关系上95.................................................................6.3.1时间t95................................................................................................................6.3.2 R'是一台发动机的发动机转速......................................................................................6.4 对该领域的结论101参考书目103集群动力学实验115B Twitter上的composantesgéantes示例119C Python123中的步骤连续采样D 步骤连续采样125VimontGuillaume-T'hesededoctorat-2019年10月12128-VIMONTGUILLaume-T'hesededoctorat-2019年10月- 13128-简介随着F ace b o ok和Twitter等W eb平台的出现，社交网络不再是我们日常生活的一部分。虽然网络及其分析在科学中并不是一个非常丰富的研究领域[60，21，22]，但互联网和计算机应用的发展使来自世界各地的大量礼物以礼物的形式被分析和处理。来自传统礼物的礼物与在礼物探索中使用的传统礼物有很大的不同。 除了它们的巨大规模之外，捐赠主要是由用户进行的，因此是非结构化的和非结构化的，与朋友和朋友等社会关系有关。这个新的捐赠者网络需要我们应用捐赠者网络的计算分析，这可能会将特定的理论与捐赠者网络的探索统计数据结合起来[6，14，50，44]。在这篇文章中，我们将讨论s或ciaux图，或者它们是如此的固定。这不是以fluxdedees的形式出现的，不，我们将推导出ap-pro ces算法，这些算法将approximer它们的簇，而不需要sto ck er整个图。这个聚类分析的第一个问题是一个总问题[3，63，11，19，18]，特别是在伊斯利·克莱的书&中[22]，书中将礼物分析与经济价值联系起来。2015年，这四篇论文的工作[12，32，46，27]集中在密集子g中缝的pourhole ver算法解上，b的apartir在后面的naireO（n）inm中，来自论文[8]。其中一个问题是，使用n'tdenou velleshy pot eses，在不存在的集合中，用一个记忆子系来识别一个V。VimontGuillaume-T'hesededoctorat-2019年10月14128-√√本论文的主要成果是描述了内存流算法的子部分。然后，我们同意在此框架内进行几次失败的尝试，并最终确定捐赠的规模。主要结果是：— 我们在s或ciaux图上使用hy pot h'ese：g的分布遵循e幂律。 从man i'ereplusp'ecise，我们将mo ntrera v与O（n）的记忆。（n）），在尺寸为O（n）的孔中，p是可能的— 让我们定义一个cor r'elati的概念，即n是一个集合的两个flx和一个距离e n tre fl x，然后将其"扩展"到一个距离e n tre标签。然后，我们在这些距离上，从而在这些关系上，创造了一个发动机。VIMONTGUILLaume-T'hesededoctorat-2019年10月- 15128-√√上下文因此，没有人会把他们的罪归咎于罪，也没有人会把他们的罪归咎于罪。 这些图表是结构性和统计性的。我们如何在这些捐赠者的数据上使用这些专有的算法？在一个图a eat oireErdos-Renyi中，所有食物的度分布遵循高斯定律。 这个penda nt，s或ciaux图的度r的分布，所以不是homo genesma ，是一个幂律。它们 在这些顶点群[34，37]中的密度可能更大，因此也不是一个簇。 S或Ciaux图的这种特征是不规则的，我们可能会看到一个簇或一个com munau te作为一个大的NSE子图。聚类的选择和估计是一个重要的我们将在一个集合的集合中尝试聚类的近似，使用图的动态分块的技术，并使用n个结构演变从e cha ntillons开始。 该算法适用于分析e c ha n tillons的相关com p osa ntes。这是一个很大的问题，也是一个很大的问题。当开发由水和水组成的系统时，我们从AP P Orter那里得到了解决方案，这些系统在大小、噪音和动态性方面都很重要。特别地，我们将在具有m = O（n log（n））的图1中尝试具有足够大的O（n）量级的簇。一个R。如果我们有一个大小为O（√n）的CL，那么我们p或v将用我们的算法rithmeba s'eon e c ha n tillation from a reser voir ， the etection of thegroup. 在clu'ter的大小为O（n）的情况下，我们在实践中发现，etecte '的算法也是n个聚类，但我们没有p或v个gara n个命中。我们将证明，根据幂律，测试网络的大小是否大于某个阈值的算法是一个很好的解，即在遵循度分布的图中选择1. 如果一个图的r度分布遵循幂律，那么r的O（nlog（n））VimontGuillaume-T'hesededoctorat-2019年10月16128-√-2贡献我们有一个方法来在一个由一个集合的一个集合定义的集合的一个集合的集合中获取聚类，它的ns （n）。集群检测的主要结果是：— 如果图中有一个大小大于a'O（√n）的γ -簇2，我们将p或v必须借助reservoir的echantiloning来检验这个簇a v的存在性。我们也在2号的consi d'era nt中看到这是一个很好的例子，也是一个很好的例子。因此，如果图是一个遵循这个统计定律的图，我们从emo ntrer到v，很有可能不存在聚类。 这些结果将在第4章中详细说明。— 我们已经将这种技术扩展到由时间有限的动力学图。 如果我们有一个动态图，其中在某个时间出现了一个大聚类p，我们将用概率的n个gra来表示它。如果没有大的聚类，我们将p或v必须以很大的概率检测到v不存在。 这些结果将在第5章中详细说明。通过算法对大聚类的检测使得能够考虑多个捐赠流的相互作用Don nes聚变是信号理论中的一个主题，它也使用近似非离子。礼物的概念是在礼物的基础中使用的一个概念，当礼物的几个来源不存在时，但在一般情况下，没有近似或ximation。我们使用聚类近似来定义流的c或r关系以及r/che/p/r/r关系的原理— 我们不需要定义两个flux的corrérelationdecntenρ（t），就像Jaccard在时间t的fen中它们的簇的联合的类似t'e我们提出了一个简单而有效的方法来应用我们的在线关系和MOntron，因为我们的图具有遵循幂律的动态随机性，我们可以保证一个很好的近似。— 通过分析fl x的关系，我们p或v确定了fl x之间的距离，并构建了一个生成这些nce的基因 我们将两个标签之间的距离定义为扩展的距离，并在这些距离上构建一个搜索引擎。第六章介绍了FLUX SO N T P NE这项研究结果的应用之一是 我们不计算这些在线fl的cor relati ons。因此，我们不应该把它们放在一个词的后面，或者把它们放在一个词的后面，或者把它们放在另一个词的后面，或者把它们放在另一个词的后面。他们是如此之多或如此之少。2. γ-聚类是一个稠密的子图，其中γ。|...|. |S|-1因此，n个字母的数字由下式定义：|E（S）|≥VIMONTGUILLaume-T'hesededoctorat-2019年10月- 17128-因此，它们的解释与它们的关系是一致的，也是不一致的。那么，我们如何分析我们的水服务和我们的水服务呢？在伊斯利·克莱的书中，有两个主题是不可能的。[22] FLS的算法和DonNE的积分。因此，这不是这两个x主题，因此是这个t 'ese的共同贡献。在概率意义上，它们的算法并不适用，而且它们也不适用于定义一个近似于给定值的度量。这是关于酒吧许可证的一个很好的例子：— 多个流媒体边缘的内容相关性，IEEE大数据国际会议，2018年 。— 应用程序roximate我ntegration的流媒体data，输入不存在的问题和— App roximateI ntegrationofstreamingdata，（2017 年文章的版本，在SpringerInformation 系 列 的 e a r ch ， int e g r ation ， and p ersonalization2019 [26]中）。— 分析查询对社交网络的价值，社交网络中的大数据挖掘研讨会，IEEE大数据国际会议，2015年。VimontGuillaume-T'hesededoctorat-2019年10月18128-T'ese的组织在第一章中，我们推导出图理论的概念，特别是将图理论的概念与随机数联系起来。我们将在集群中创建您的帐户。在第二章中，我们讨论了Twitter的具体内容。我们将从这个特殊的网络中提取几个样本，然后我们将把这些样本转换成一个文件，一旦它们在图中出现，就可以分析它们的在第三章中，我们把经典的集的metho映射到一个已知的图中。在第4章中，我们将讨论如何在一个图中近似聚类的方法。 我们在静止的太阳上创造了一个或另一个太阳。这在第5章中，我们研究了动态ES O图中的R S簇集。在这些图中，没有任何关于聚类的近似或ximation，也没有任何关于动态网络的近似或ximation ba。在这些方法中，我们有我们的算法，在第6章中，我们将从原始集合中导出的clu s t ss 在第二步中，我们在这些距离上建立了一个搜索引擎，从而在这些动态图形流的关系上建立了一个搜索引擎。VIMONTGUILLaume-T'hesededoctorat-2019年10月- 19128->1图形和reseauxsociaux数学分析在其算法和度量中使用了几个数理概念。数理理论为我们提供了工具来表示形式上的关系，并确定关系的结构特征。本节中的定义在很大程度上遵循了Biggs[13]和Bollob'as[15]的定义。1.1他或她对图形感到惊讶。一个reseau被定义为一个o bjetcom po s的ent通过某些连接相互作用。在自然界中，表示resent ermath的m o y在数学上是通过图的m o。1.1.1从定义tions一个图G由一个由节点V组成的ensem和一个由节点E组成的ensem组成L’ensem五.他们的名字是VEN如果图是度量的，则为无无一个子图G可以从G中选择n个子元mbleV的Vs，或E的子项mbleEs。一个子图G是从子元mbleVspn是连接Vs中n个节点的G的所有节点。子图Gs n是从E的子元m ble E s开始的，pp对网络的分析主要使用由节点组成的子图。两个节点，其中一个是在Com m aso ntadjace nts中，另一个是在m m m ma n t a n t a n n n t adjace n ts中，另一个是在m m m a so ntadjace nts中。 在非定向的g条中，在s对中有孔的节点是通过说唱p在节点处发生的，并且R在节点处通过说唱p在节点处发生的。对于有向图n，从u1到u2的a是从u1入射的nteau2，并且是从u1入射的nte。VimontGuillaume-T'hesededoctorat-2019年10月20128-Σ德格雷。因此，一个人的灵魂是一个人的灵魂，一个人的灵魂是一个人的灵魂，一个人的灵魂是一个人的灵魂。E'ntdon'e是一个度量图syG=（V，E）一个节点u的s度r之和由方程d（u）= 2 |E|（1.1）u>V在图n中，我们p或von区分节点u的e度r，其有限度rentrantd−（u）作为指向节点u的agees的n个成员，而有限度r e sortan t d +（u）作为节点u的agessortants的n个成员丹西特。图G=（V，E）的稠密度由p或n定义，n是一个Rsdivise的数目，n是一个R s可能的数目。因此，n个非有向图的密度teD=2|E||·（|V|（1）|− 1)对于一个有ne的图，densite等于：D=|E||* （|V|（1）|− 1)请注意，r和e的最大bre数|* （|V|（1）2|− 1) 2（1.2）（1.3）（1.4）另一个有用的概念是有限图的度remoyen或连通性te，2|E|...（1.5）|V|1.1.2度的分配在非有向图G=（V，E）中，r的分布由下式定义：P（k）=|{u i}V：度ui= k}|（1.6）|E|