0
$\begingroup$

Context

I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = 22$ means that amongst all edges the edge $e$ was visited $22$ times.

Approach

Given two vertices $v,v'$ in $G$, how can I find the "most popular path" ? Knowing the fact finding the max weight path in cyclic directed graph is NP-hard, I changed my approach in the following way:

  • Normalize the weights to have probabilities $p(e) = \dfrac{w(e)}{Z_w}$ with $Z_w = \sum_{e\in E} w(e)$
  • Set the cost of a path $P = (e_1,e_2,\dots, e_n)$ as a decreasing function of the product of probabilities $\prod_{i=1}^n p(e_i)$,
    for example use the Negative Log Likelihood $\ell(P) = -\sum_{i=1}^n\log p(e_i)$
  • Use a shortest path algorithm which minimizes the NLL of a path between $v,v'$ to approximate the most popular path. This can be done via setting new weights $\tilde{w}(e) = -\log w(e) + \log Z_w$

Question

Is this approach at least partially correct? Can I trust its results? I will conduct a statistical experiment (on random graphs) later today and post results. Any contribution is appreciated!

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ What is your definition of "most popular path"? What do you mean by "correct"? Correct according to what specification or what requirements? Correctness means that it meets all of the requirements, but as you haven't stated any requirements, I don't think we can answer whether it is correct or not. I don't know what you mean by "trust its results". It sounds like you are asking "will this give me the results I want?" but as we don't know what you want it is likely going to be hard to answer. $\endgroup$
    – D.W. ♦
    Commented Jan 17, 2021 at 20:03
  • $\begingroup$ @D.W. well for example ideally I would have a list of all possible paths in the graph and the probability of each path. This means many path might go from $v$ to $v'$, but as there are probabilities assigned to each path I can find the path with highest probability $\endgroup$
    – NoVariation
    Commented Jan 17, 2021 at 20:07
  • $\begingroup$ I suggest you spend some more time to think about your problem and how to articulate a specific question about it. Your comment seems different from what is in the question. The question says nothing about listing all possible paths. Listing all possible paths is very different from finding a single path. It's going to be frustrating if we have to go through several rounds of comments to understand what you are asking, so I encourage you to think about it and figure out how to present it clearly so we don't have to do that. $\endgroup$
    – D.W. ♦
    Commented Jan 17, 2021 at 20:09
  • 1
    $\begingroup$ Is your goal to find the path that has the highest probability assigned to it, where its probability is the product of the probabilities of its edges, and the probability of the edge is as given in the question? And is your question whether the algorithm you have is a correct algorithm for that task, i.e., it does output that path? $\endgroup$
    – D.W. ♦
    Commented Jan 17, 2021 at 20:19
  • 1
    $\begingroup$ That's not a good fit for this site. This site is aimed for specific, narrowly focused, objectively answerable technical questions. "Any contribution is interesting" is outside the scope of this site. "How wrong is it?" is probably not answerable. "Could I model this better?" is probably not answerable with the question you've given us, since that requires a lot more context. Also that's too open-ended and broad; we want a single focused question. See our tour and cs.stackexchange.com/help/how-to-ask. $\endgroup$
    – D.W. ♦
    Commented Jan 17, 2021 at 20:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.