读图数据库实战笔记10图分析

1. 图分析

1.1. 图分析和机器学习（ML）是进一步探索图时要探索的两个最常见领域
1.2. 寻路

• 1.2.1. 每一个特定的寻路算法的工作原理都略有不同，并且各有优缺点
  
• 1.2.2. 测向
  
  
  
  • 1.2.2.1. 地理制图工具使用寻路算法的一些变体来提供方向
    
  
  
• 1.2.3. 优化标题
  
  
  
  • 1.2.3.1. 寻路算法可以优化处置惩罚大量相互依靠的实体的各种标题，从管理供应链到优化金融交易，再到确定盘算机网络中的瓶颈和故障点
    
  
  
• 1.2.4. 欺诈检测
  
  
  
  • 1.2.4.1. 许多欺诈算法使用循环检测，发现与自身相连的实体组，以探求紧密相连的子图，作为潜伏欺诈账户的衡量尺度
    
  
  
• 1.2.5. 最常见的寻路算法是最短路径算法，它盘算两个顶点之间的最短路径
  
  
  
  • 1.2.5.1. 无加权方法将所有路径视为相等的，根据所遍历的边数盘算最短路径
    

    1.2.5.1.1. 社交网络就是说明无加权最短路径算法有用的一个好例子
    

    
    
  • 1.2.5.2. 加权方法为所有路径分配相对权重，然后在盘算中使用这些权重
    

    1.2.5.2.1. 当遍历边的相对本钱不相等时，加权最短路径算法是一个很好的选择
    

    1.2.5.2.2. 供应链优化
    

    1.2.5.2.2.1. 移动货品的相对本钱（距离/时间）是不相等的
    

    1.2.5.2.3. 网络路由标题
    

    1.2.5.2.3.1. 硬件或其他方面的缘故原由（如地理相近）​，连接之间传输网络数据包所需的时间也不同
    

    
    
  
  
• 1.2.6. 最常见的是Djkstra算法和A*搜索算法，它们都可用于加权图和无加权图
  

1.3. 中心性

• 1.3.1. 重要性一词来描述一个特定顶点在图整体布局中起的作用
  
• 1.3.2. 顶点重要性的具体含义根据特定算法所盘算的内容而异
  
• 1.3.3. 每个方法都是定义重要性的完美有效方法，但盘算每个方法都可能会产生不同的结果
  
• 1.3.4. 度数
  
  
  
  • 1.3.4.1. 度数（degree）中心性是最容易理解的
    
  • 1.3.4.2. 度数是指与一个顶点干系联的边的数量，因此度数中心性是基于边数对顶点举行排序的
    
  • 1.3.4.3. 度数中心性可以通太过别测量内度和外度来进一步细分
    
  • 1.3.4.4. 度数中心性通常用于确定图连接水平的基线，尤其是在盘算均匀值、最小值和最大值时
    
  
  
• 1.3.5. 间隙
  
  
  
  • 1.3.5.1. 间隙（betweenness）中心性是指一个顶点在图中所有节点对之间的最短路径中被使用的次数
    
  • 1.3.5.2. 间隙中心性在探求连接不同顶点组的临界点方面很有效
    
  • 1.3.5.3. 使用该算法时，返回的数越大，表示该顶点越重要。如果在
    
  • 1.3.5.4. 如果在我们的社交网络中运行间隙中心性，就能发现谁与不同的社会群体有最多的接洽
    
  
  
• 1.3.6. 密切度
  
  
  
  • 1.3.6.1. 密切度（closeness）中心性是对从一个顶点到所有其他顶点的最短路径均匀长度的度量，表示相对于所有其他顶点，哪些顶点位于最中心的位置
    
  • 1.3.6.2. 使用密切度数中心性时，返回值越小，说明该顶点越重要
    
  • 1.3.6.3. 在我们的社交网络中运行密切度中心性，就能识别出哪些人是社交网络的“核心”​
    
  
  
• 1.3.7. 特征向量
  
  
  
  • 1.3.7.1. 特征向量（eigenvector）中心性是一种复杂的中心性测量，使用相邻顶点的相对重要性作为输入来盘算给定顶点的重要性
    
  • 1.3.7.2. 仅凭一个顶点与许多其他顶点相连，并不一定能说明它很重要
    
  • 1.3.7.3. 应该使用相邻顶点的重要性来盘算该顶点的总体重要性
    
  • 1.3.7.4. 在我们的社交网络中运行特征向量中心性，可以找到社交网络中最有影响力的人，他们不仅拥有最多的接洽，而且这些接洽很紧密
    
  
  
• 1.3.8. PageRank
  
  
  
  • 1.3.8.1. PageRank是由于被Google的拉里·佩奇和谢尔盖·布林用于对搜索结果举行加权而出名的一种算法
    
  • 1.3.8.2. 使用相邻顶点的相对重要性来帮助确定顶点的总体重要性
    
  • 1.3.8.3. 包罗一个衰减值（通常设置为0.85）​，以指示随着网络的遍历，影响会徐徐衰减
    
  • 1.3.8.4. 顶点的PageRank返回值越高，该顶点就越重要
    
  • 1.3.8.5. 与特征向量中心性一样，如果在我们的社交网络中运行PageRank，结果将代表在社交网络中最有影响力的人
    
  
  

1.4. 群体检测

• 1.4.1. 群体检测（community detection）算法来发现相互紧密连接但与图中其他顶点疏松连接的顶点组或群体
  
• 1.4.2. 群体检测算法不仅仅范围于社交网络，还被用于许多行业和用例
  
• 1.4.3. 与中心性算法一样，有大量潜伏的群体检测算法，每个算法都以轻微不同的方式找到群体
  
• 1.4.4. 三角形计数
  
  
  
  • 1.4.4.1. 盘算图中三角形的数量称为三角形计数
    
  • 1.4.4.2. 三角形计数在捕获图中顶点网络的内聚性或紧密性方面很有用
    
  • 1.4.4.3. 含紧密关联网络或社区的图具有较高的三角形计数
    
  • 1.4.4.4. 包罗疏松连接网络的图具有较低的三角形计数
    
  
  
• 1.4.5. 连通分量
  
  
  
  • 1.4.5.1. 在图论中，将每个顶点都有一条到所有其他顶点路径的子图称为分量
    
  • 1.4.5.2. 连通分量在全局图中发现干系数据的集群，这有助于在社交图中查找家庭、查找有接洽的组织或在电商网站中查找可能重复的账户
    
  • 1.4.5.3. 弱连通分量算法
    

    1.4.5.3.1. 算法没有考虑顶点之间边的方向
    

    
    
  • 1.4.5.4. 强连通分量算法
    

    1.4.5.4.1. 在本质上和弱连通分量是一样的，只是考虑了边的方向
    

    1.4.5.4.2. 在强连通分量中，子图中任意两个顶点之间存在一对边，每个方向上都有一条边
    

    1.4.5.4.3. 强连通分量算法来检测图中有方向性的高度连接群体
    

    1.4.5.4.4. 经常用于在金融风控领域查找欺诈活动的中心
    

    1.4.5.4.5. 经常用于在产品保举中探求相似的用户群体
    

    
    
  
  

1.5. 图和机器学习

• 1.5.1. 有讽刺意味的是，只管许多ML技能严重依靠图来完成其学习，但这些技能既不允许将图作为输入，也不允许将图作为输出
  
• 1.5.2. 大多数尺度的ML算法还是将固定向量或数据矩阵作为输入
  
  
  
  • 1.5.2.1. 向量操纵比在图上的类似操纵更简单、更快
    
  • 1.5.2.2. 可用的许多算法和工具都针对向量操纵举行了优化
    
  • 1.5.2.3. 很少有人将图作为输入数据来构建
    
  
  
• 1.5.3. 特征提取
  
  
  
  • 1.5.3.1. 在ML中使用图的最简单方法是提取图的特征，以深入了解图中的数据
    
  • 1.5.3.2. 最短路径
    

    1.5.3.2.1. 取一个人和已知的不良行为者之间的最短路径，作为欺诈ML模型的猜测度量
    

    
    
  • 1.5.3.3.  三角形计数
    

    1.5.3.3.1. 在社交网络中使用三角形计数来确定特定用户的社交性或反社交性
    

    
    
  • 1.5.3.4.  度数
    

    1.5.3.4.1. 使用顶点的连接度来确定传感器在传感器网络中的重要性
    

    
    
  
  
• 1.5.4. 图嵌入
  
  
  
  • 1.5.4.1. 图嵌入是一种将图的稀疏多维布局表示为向量或矩阵的机制
    

    1.5.4.1.1. 将稀疏数据转化为更紧凑的向量表示
    

    
    
  • 1.5.4.2. 大部分研究是由天然语言处置惩罚（NLP）方面的工作推动的，但它如今被更普各处应用于图中，为猜测新的友谊和发现欺诈活动等任务提供输入
    
  • 1.5.4.3. 顶点嵌入
    

    1.5.4.3.1. 将每个顶点表示为一个向量/矩阵，用于比力顶点级别的项
    

    
    
  • 1.5.4.4. 图嵌入
    

    1.5.4.4.1. 将整张图/子图表示为一个向量/矩阵，用于对整张图举行相互比力
    

    
    
  • 1.5.4.5. 挑战是确保我们包罗的任何特征都能充实表示拓扑、连通性和其他图属性，同时最大限度地减小向量的大小
    
  • 1.5.4.6. 更大的嵌入需要更多的处置惩罚时间和存储空间，但也保持了原始图数据的高保真度
    
  
  
• 1.5.5. 特征工程本身就是一门完备的学科
  

2. 其他资源

2.1. 图论

• 2.1.1. Sarada Herke的“Graph Theory Channel”​
  
• 2.1.2. Richard J. Trudeau的Introduction to Graph Theory
  
• 2.1.3. Douglas B. West的《图论导引（第2版）​》​
  

2.2. 图数据库

• 2.2.1. Ian Robinson等人的《图数据库》
  
• 2.2.2. Denise Gosnell和Matthias Broecheler的The Practitioner's Guide to Graph Data
  
• 2.2.3. Kelvin R. Lawrence的PRACTICAL GREMLIN: An Apache TinkerPop Tutorial
  
• 2.2.4. Corey L. Lanum的Visualizing Graph Data
  

2.3. 图数据集

• 2.3.1. Stanford Network Analysis Project（SNAP）
  
• 2.3.2. Kaggle
  
• 2.3.3. Google Datasets
  
• 2.3.4. LDBC（Linked Data Bench Council）的The Social Network Benchmark（SNB)
  

2.4. 图算法

• 2.4.1. Tushar Roy的“Coding Made Simple, Graph Algorithms Playlist”​
  
• 2.4.2. Algorithms Course的“Graph Theory Tutorial from a Google Engineer”​
  
• 2.4.3. Alessandro Negro的Graph-Powered Machine Learning
  
• 2.4.4. Mark Needham和Amy E. Hodler的《数据分析之图算法：基于Spark和Neo4j》
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。