1
$\begingroup$

Problem

I have the following directed tripartite graph $G(E\cup V\cup P, A)$, where there is a many-to-one symmetric relationship between the subsets V and E - $e\in E,v\in V,[e, v]\in A \iff [v, e]\in A$ - and a many-to-many relationship between the subsets P and V. All edges $[x, y]\in A$ have a weight $w_{xy}$ which determines the portion of score that will be propagated from node x to y. $$\forall_{x\in G}\sum_{y\in G}w_{xy}=1\\\ [x, y] \notin A \iff w_{xy}=0 $$ I got the following naive equations, where $SP_t(p)$ is the Score of "p" at iteration "t" (same for SV and SE), $SP_0(p)$ is the starting score of "p": $$ SP_{t+1}(p)=SP_0(p)+\sum_{v\rightarrow p}SV_t(v)w_{vp},\\\ SV_{t+1}(v)=SV_0(v)+\sum_{p\rightarrow v}SP_t(p)w_{pv}+\sum_{e\rightarrow v}SE_t(e)w_{ev},\\\ SE_{t+1}(e)=SE_0(e)+\sum_{v\rightarrow e}SV_t(v)w_{ve}.\\\ (1) $$ I want to compute the scores of each node in a way that I can rank those nodes within their subset. If a node's neighbors are high ranked, then this node is also high ranked.

Generalization

I think what I am trying to do here is resolve a kind of random walk over G, the scores are random variables since a node's score depends on other nodes pointing to it. This problem can be modeled as a Markov Chain, I need to find the fraction of time the random walker spends at each node in G (it is the normalized score).

Related algorithms

Searching I found the algorithms PageRank and Generalized Co-HITS that solves similar problems, PageRank was designed for unipartite graphs and Generalized Co-HITS designed for bipartite graphs.

The PageRank(PR) of a page "p" is given by $PR_{t+1}(p)=(1-a)\frac 1n+a\sum_{u\rightarrow p}PR_t(u)\frac 1{d_u^+}$ - where "p" and "u" are nodes, "n" is the # of nodes, "a" is the "damping factor", $d_u^+$ is the outdegree of "u".

1) I see that I could use it but I am not sure if it will compute an accurate score to rank nodes within their subsets, because PR will rank all nodes within the superset P + V + E. Am I right?

Generalized Co-HITS looks like PR. Consider just two subsets P and V which makes a bipartite graph: $$ SP_{t+1}(p)=(1-a)SP_0(p)+a\sum_{v\in V}SV_t(i)w_{vp},\\\ SV_{t+1}(v)=(1-b)SV_0(v)+b\sum_{p\in P}SP_t(p)w_{pv}.\\\ (2) $$ I tried to adapt it to a tripartite graph based on system (1). I substituted SV in SP and SE: $$ SP_{t+1}(i)=SP_0(i)a+(1-a)b\sum_{j\in V}W_{ji}^{vp}SV_0(j)+(1-a)(1-b)\left[\sum_{m\in P}\left(\sum_{j\in V}W_{mj}^{pv}W_{ji}^{vp}\right)SP_t(m)+\sum_{n\in E}\left(\sum_{j\in V}W_{nj}^{ev}W_{ji}^{vp}\right)SE_t(n)\right],\\\ SV_{t+1}(j)=SV_0(j)b+(1-b)\left(\sum_{m\in P}W_{mj}^{pv}SP_t(m)+\sum_{n\in E}W_{nj}^{ev}SE_t(n)\right),\\\ SE_{t+1}(k)=SE_0(k)c+(1-c)b\sum_{j\in V}W_{jk}^{ve}SV_0(j)+(1-c)(1-b)\left[\sum_{m\in P}\left(\sum_{j\in V}W_{mj}^{pv}W_{jk}^{ve}\right)SP_t(m)+SE_t(k)\sum_{j\in V}W_{kj}^{ev}W_{jk}^{ve}\right].\\\ (3) $$ and got a weird system. Here I swapped "a", "b", and "c" (all acts like damping factors) positions, now they multiply the starting score. $W_{}^{pv}$ is the weight matrix from P to V. But I changed the end of 3rd equation: $$ \sum_{n\in E}\left(\sum_{j\in V}W_{nj}^{ev}W_{jk}^{ve}\right)SE_t(n) \equiv SE_t(k)\sum_{j\in V}W_{kj}^{ev}W_{jk}^{ve} $$ because of the many-to-one symmetric relationship between V and E, there is no transitive relationship between different nodes in E through edges to V (but it may happen in paths like $e_1\rightarrow v_1\rightarrow p_1\rightarrow v_2\rightarrow e_2$).

Co-HITS does not impose any constraint except the graph being bipartite and all out-edges' weight (probability) for any node sums up to 1. There is a hidden bipartite graph, with nodes $P\cup E$, made by transitive relationship through V, it shows up in system (3). However, the total weight of that transitive edges is not equal to 1, $\sum_{e\in E}w_{ev}w_{vp}\ne 1$ and $\sum_{p\in P}w_{pv}w_{ve}\le 1$. The same happens if I take $P\cup V$ or $V\cup E$. The joint in V splits the weights to the opposite sides P and E. That is, the probability of being in "e", going to "v" and then going to "p" is different from being in "e" and going to "p", because when being in "v" there is a probability of going back to "e". So system (3) is not a valid adaption of Co-HITS (2).

2) Is system (3) solvable with iterative method employed by original PageRank?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.