Durable relationship prediction and description using a large dynamic graph

Dynamic graphs are a data structure widely used in representing changeable relationships or connections between different entities. This paper proposes a novel type of node similarity, based on the frequency of connections between nodes to describe the changeable relationships between entities over a period; this has not been considered before as an indication of similarity between two nodes. In other words, if two entities have a history of frequent connections, this means that they have something in common and have a durable relationship. In this paper, durable relationships describe the frequency of connections rather than only the continuous connection between two nodes. Thus, durable relationships are defined in two dimensions: (i) In the dimension of time, they can be categorized based on the length of duration as short-term, medium-term, or long-term relationships; (ii) Based on frequencies of connections over a period, they can be categorized into four statuses (No Relationship, Weak Relationship, In Relationship, and Strong Relationship). Based on this definition of durable relationships, a node similarity measurement algorithm is proposed, to study the status of relationships from a longitudinal study point of view. This method provides a new way to describe the semantics of relationships (such as collaborative relationships, or customer loyalty descriptions) and also gives a practical application of node similarity measurement in a real world, which is to provide a prediction of relationship. Our extensive experiments have shown that the proposed method can effectively describe durable relationships and especially predict future relationships.