Using Random Walks to Generate Associations between Objects

Measuring similarities between objects based on their attributes has been an important problem in many disciplines. Object-attribute associations can be depicted as links on a bipartite graph. A similarity measure can be thought as a unipartite projection of this bipartite graph. The most widely used bipartite projection techniques make assumptions that are not often fulfilled in real life systems, or have the focus on the bipartite connections more than on the unipartite connections. Here, we define a new similarity measure that utilizes a practical procedure to extract unipartite graphs without making a priori assumptions about underlying distributions. Our similarity measure captures the relatedness between two objects via the likelihood of a random walker passing through these nodes sequentially on the bipartite graph. An important aspect of the method is that it is robust to heterogeneous bipartite structures and it controls for the transitivity similarity, avoiding the creation of unrealistic homogeneous degree distributions in the resulting unipartite graphs. We test this method using real world examples and compare the obtained results with alternative similarity measures, by validating the actual and orthogonal relations between the entities.

基于属性度量对象间的相似度，是诸多学科领域的重要研究问题。对象-属性关联可被表征为二分图（bipartite graph）上的连边，而相似度度量可被视为该二分图的单部投影（unipartite projection）。当前应用最广泛的二分图投影技术，要么做出了现实系统中难以满足的假设，要么更侧重二分图层面的连边而非单部图层面的关联。本文提出一种全新的相似度度量方法，其采用实用的单部图提取流程，且无需对潜在分布做出先验假设（a priori assumptions）。该相似度度量通过随机游走者（random walker）在二分图上依次经过两个节点的概率，来刻画二者间的关联程度。该方法的一项核心优势在于，对异构二分图结构具备鲁棒性，同时可控制传递性相似度，避免在生成的单部图中出现不符合现实的均匀度分布。本文通过真实世界案例对该方法进行测试，并通过验证实体间的实际关联与正交关系，将所得结果与其他相似度度量方法进行对比。