数据处理 · 初步的认识关系图(三)

此篇讲一下关系图片中的特征和有向图
一、 关系图特征值

1.最大的度(Max Degree)

在关系图谱中每一个顶点的度是图论算法中非常重要的计算对象。如果某一个节点的度最大,则说明他很有可能是这个关系图中的核心点。

寻找一个关系图谱中带有最大度数的顶点并不困难,只需全部先计算出所有顶点的度,然后找出最大数即可。

当然,光是找出最大的度可不能满足算法的需要。除了找出最大的度数以外,自然还需要知道是哪一个顶点具有最大的度数。所以我们需要准备两个函数,一个用于找出带有最大度数的顶点,而另外一个则用于获取其度数。

//Graph是总的关系图类
class Graph { 
    // ... 
    largestVertex() { 
        const self = this 
        const degrees = self.vertexIds.map(function(vertexId) { 
            return { 
                degree: self.degree(vertexId), id: vertexId 
            } 
        }) 
        return self.getVertex(_.maxBy(degrees, 'degree').id) 
    } 
    maxDegree() { 
        return this.degree(this.largestVertex().id) 
    } 
} 
const vertices = [ 
    new Vertex(1, 'A'), 
    new Vertex(2, 'B'), 
    new Vertex(3, 'C'), 
    new Vertex(4, 'D'), 
    new Vertex(5, 'E') 
    ] 
const edges = [ 
    new Edge(1, 2, 1), 
    new Edge(1, 3, 2), 
    new Edge(2, 4, 1), 
    new Edge(3, 4, 1), 
    new Edge(1, 4, 2), 
    new Edge(4, 5, 3) 
    ] 
const graph = new Graph(vertices, edges) console.log(graph.largestVertex().property) //=> D 
console.log(graph.maxDegree()) //=> 4 

2、自环(Self-Loop)

自环是一种十分抽象的概念,其定义是在一个关系图谱内,某一个顶点存在一条边再与自己相连。我们可以将一个关系图谱中的每一个顶点看作是事件序列中的某一个事件,顶点间的边则表示多种情况下事件之间的连续关系。那么在这种场景下,顶点的自环就可以被解释为某一个事件的连续发生可能性。

在多种事件顺序发生的可能性中,如果某一个事件的连续发生次数(我们可以使用边的属性值表示)越多,则表示该事件的重要性越强。这种概念在一些对用户行为进行分析的应用中十分重要。

而找到自环的边的方法也非常简单,只需要找到那些左右顶点相同的边即可。

class Graph { 
    // ... 
    loops() { 
        const self = this 
        return self.edgeIds 
            .map(function(edgeId) { 
                return self.edges[edgeId] 
            }) 
            .filter(function(edge) { 
                return edge.leftId === edge.rightId 
            }) 
        } 
    } 
    const vertices = [ 
        new Vertex(1, '1'), 
        new Vertex(2, '2'), 
        new Vertex(3, '3') 
        ] 
    const edges = [ 
        new Edge(1, 1, 3), 
        new Edge(1, 2, 1), 
        new Edge(1, 3, 1), 
        new Edge(2, 3, 2) 
        ] 
    const graph = new Graph(vertices, edges) 
    console.log(graph.loops()) //=> [ Edge{ leftId: 1, rightId: 1, property: 3 } ] 

二、有向图

有向图是从原本的一条边即代表两个顶点共同拥有一个平等的关系,变成允许顶点之间存在单向的关系。就好像我们在人际社交中,朋友之间互相认识所以我们是平等的,但是我们也有很多我们只认识他们,他们却不认识我们的人

  1. 有向边

因为我们前面第一篇所定义的边是不存在方向特性的,所以我们直接使用了 leftId 和 rightId 来存储与边相连的两个顶点的信息。而有向图的边是带有方向特征的,虽然我们也可以像数学一样定义一个向量的表达方式就是从左到右的(如 ),直接使用前面所定义的边来表示有向边,但是我们还是需要另外定义一个有向边类型以使用。

class DirectedEdge { 
    constructor(originalId, targetId, property) { 
    this.originalId = originalId 
    this.targetId = targetId 
    this.property = property 
    } 
} 
  1. 有向图 Digraph

因为使用的边不再是无方向特性的边,所以之前所定义的其实是无向图类型,不能直接当做有向图使用了。有向图和无向图最大的区别就是顶点之间从平行的关系变成了有出或入的单边关系。出则代表着某一个顶点存在一个单向的关系指向另外一个顶点,而入则表示某一个顶点被另外一个顶点所指向。

那么前面使用 edgeRelations 来存储顶点与边的关系时则需要加以改动了,我们可以简单地分开 inEdgeRelations 和 outEdgeRelations 来分别存储顶点与入边、出边的关系。

class Digraph { 
    constructor(vertices, edges) { 
        // Vertices 
        this.vertexIds = [];
        this.vertices = {};
        for (let i = 0; i < vertices.length; ++i) { 
            const vertex = vertices[i];
            this.vertexIds.push(vertex.id); 
            this.vertices[vertex.id] = vertex;
        } 
        const edgesWithId = edges.map(function(edge, i) { 
            edge.id = i + 1; 
            return edge; 
        }) 
        // Edges 
        this.edgeIds = []; 
        this.edges = {}; 
        this.inEdgeRelations = {}; 
        this.outEdgeRelations = {}; 
        for (let i = 0; i < edgesWithId.length; ++i) { 
            const edge = edgesWithId[i]; 
            this.edgeIds.push(edge.id);
            this.edges[edge.id] = edge;
            if (typeof this.outEdgeRelations[edge.originalId] === 'undefined') {                 this.outEdgeRelations[edge.originalId] = []; 
            } 
            if (typeof this.inEdgeRelations[edge.targetId] === 'undefined') {                    this.inEdgeRelations[edge.targetId] = []; 
            }                                                                               this.inEdgeRelations[edge.targetId].push(edge.id)                                this.outEdgeRelations[edge.originalId].push(edge.id) 
        } 
    } 
} 

总结:关系图谱在社会人际关系也可以体现出来,可以分为有向图,无向图,实际例子可以举例说明,可能更加清楚关系图谱。