Direction-Aware Proximity on Graphs

In many graph mining settings, measuring node proximity is a fundamental problem. While most of existing measurements are (implicitly or explicitly) designed for undirected graphs; edge directions in the graph provide a new perspective to proximity measurement: measuring the proximity from A to B; rather than between A and B. (See Figure 1 as an example). In this chapter, we study the role of edge direction in measuring proximity on graphs. To be specific, we will address the following fundamental research questions in the context of direction-aware proximity: 1. Problem definitions: How to define a directionaware proximity? 2. Computational issues: How to compute the proximity score efficiently? 3. Applications: How can direction-aware proximity benefit graph mining?