Discovery of “Enishi”: A Generalized Flow based Analysis of Relations

Two kinds of relations exist, explicit relations, e.g. a friend, and implicit relations, e.g. a friend of a friend. Both kinds of relations have important roles in the real world. We propose a new method using a generalized maximum flow for measuring the strength of a relation. Particularly, our method mine objects constituting a relation by outputting several paths contributing to the generalized maximum flow, that is, paths along which a large amount of the flow is sent.

Furthermore, we propose a ranking tool based on the new method for measuring a relation described above to afford a better understanding of a relation or a ranking based on relations. Our ranking tool has the following three features for understanding a relation or a ranking based on relations:

  1. It visualizes several paths for explaining a relation by displaying objects important for understanding the relation;
  2. It classifies the destination objects automatically by analyzing objects constituting each relation between the source and each destination;, e.g. two groups “petroleum exporting countries” and “petroleum consuming countries” for a ranking of countries based on relations form petroleum to each country;
  3. It visualizes a graph for explaining reasons why an object has a stronger relation to a specified object than another object has, by extracting differences between objects constituting the relations.


  1. Xinpeng Zhang, Yasuhito Asano, and Masatoshi Yoshikawa, “Visualized Elucidations of Ranking by Exploiting Object Relations,” Third International Workshop on Ranking in Databases (DBRank 2009), Shanghai, China, March 29, 2009.
  2. Xinpeng Zhang, Yasuhito Asano, Masatoshi Yoshikawa, “A Generalized Flow based Analysis of Relations,” The 23rd Annual Conference of the Japanese Society for Artificial Intelligence(JSAI 2009), June 17 - 19, 2009.
project/en/enishi.txt · Last modified: 2011/11/25 05:03 by ylab