Random Walk on Multiple Networks

Random Walk is a basic algorithm to explore the structure of networks, which can be used in many tasks, such as local community detection and network embedding. Existing random walk methods are based on single networks that contain limited information. In contrast, real data often contain entities with different types or/and from different sources, which are comprehensive and can be better modeled by multiple networks. To take the advantage of rich information in multiple networks and make better inferences on entities, in this study, we propose random walk on multiple networks, <inline-formula><tex-math notation="LaTeX">$\mathsf {RWM}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">RWM</mml:mi></mml:math><inline-graphic xlink:href="luo-ieq1-3221668.gif"/></alternatives></inline-formula>. <inline-formula><tex-math notation="LaTeX">$\mathsf {RWM}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">RWM</mml:mi></mml:math><inline-graphic xlink:href="luo-ieq2-3221668.gif"/></alternatives></inline-formula> is flexible and supports both multiplex networks and general multiple networks, which may form many-to-many node mappings between networks. <inline-formula><tex-math notation="LaTeX">$\mathsf {RWM}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">RWM</mml:mi></mml:math><inline-graphic xlink:href="luo-ieq3-3221668.gif"/></alternatives></inline-formula> sends a random walker on each network to obtain the local proximity (i.e., node visiting probabilities) w.r.t. the starting nodes. Walkers with similar visiting probabilities reinforce each other. We theoretically analyze the convergence properties of <inline-formula><tex-math notation="LaTeX">$\mathsf {RWM}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">RWM</mml:mi></mml:math><inline-graphic xlink:href="luo-ieq4-3221668.gif"/></alternatives></inline-formula>. Two approximation methods with theoretical performance guarantees are proposed for efficient computation. We apply <inline-formula><tex-math notation="LaTeX">$\mathsf {RWM}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">RWM</mml:mi></mml:math><inline-graphic xlink:href="luo-ieq5-3221668.gif"/></alternatives></inline-formula> in link prediction, network embedding, and local community detection. Comprehensive experiments conducted on both synthetic and real-world datasets demonstrate the effectiveness and efficiency of <inline-formula><tex-math notation="LaTeX">$\mathsf {RWM}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">RWM</mml:mi></mml:math><inline-graphic xlink:href="luo-ieq6-3221668.gif"/></alternatives></inline-formula>.