stamps
commented
4 years ago Hi Shuai,
For the weighted/probabilistic graphs, we compute and remove a FAS f according to the unweighted graph. Thus, by definition, it will also be a FAS for the probabilistic graph. In other words, in the probabilistic graph, there is some probability that the possible worlds may NOT yield a cycle, but by removing f we ensure that the resulting possible worlds cannot contain a cycle.
Consider the following small example. Define a 3 node graph with 3 edges that form a cycle. I.e. A -> B -> C and C -> A. In the probabilistic case each of the edges comes with a probability of being present. Now, any one of these edges is a FAS for the unweighted graph. Thus, by removing any edge, say A -> B, we are guaranteed that the resulting probabilistic graph will never yield a possible world that contains a cycle. That is, the graph B -> C -> A cannot contain a cycle regardless of the presence of the probabilistic edges.
Now, the introduction of probabilities on the edges means that some cycles are much less likely to show up in a possible world than others which is how the algorithms are adapted to favour such scenarios - i.e. to minimize the weight of the edges in the FAS computed.
GreedyFAS should be easily extended to weighted graphs. The main difference is that probabilistic graphs have edge weights that are restricted to [0,1] and meant we had to deal with real valued \delta-classes. If the edge weights are restricted to integers then the extension is much simpler - you would just need to expand the range of \delta-classes beyond [3-n,n-3] to account for the maximum weight edge in the graph.
I have not kept up with the recent versions of webgraph and believe that some things have changed. I would suggest looking for a more recent tutorial or demonstration. The updates to the code should be minimal as we just use the webgraph format to read in the dataset and access edges.
Hope that helps,
Best,
Michael
On Tue, Aug 4, 2020 at 1:51 AM Shuai Wang notifications@github.com wrote:
Dear Michael Simpson,
I am Shuai Wang and I am currently a PhD student of Computer Science in the Netherlands. I have read your paper titled Efficient Computation of Feedback Arc Set at Web-Scale. I have a few questions related to this paper and I’d really appreciate it if you may answer them.
1.
For the probabilistic case of Berger-Shor algorithm, would we have the risk of having cycles after removing the FAS? Since all the arcs have a probabilistic chance of being removed, it is logical to suspect that there might be a case (even with low probability) where all the edges in a cycle are not removed. 2.
I am dealing with weighted graphs rather than probabilistic graphs. I am not an expert on graph theory. Do you think I can develop a weighted case based on your greedy algorithm presented in section 5.1.1? Any advice is more than welcome! 3.
I am not familiar with the Webgraph format. I followed your guidance on your github page for unweighted cases. But I’m not sure how to deal with weighted cases. Could you please give me a bit of guidance?
Thank you very much! Regards, Shuai Wang
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/stamps/FAS/issues/2, or unsubscribe https://github.com/notifications/unsubscribe-auth/AARMSRIEHAI4LU2UDD34BMDR67D2TANCNFSM4PUFJYCQ .
-- Michael Simpson Postdoctoral Researcher University of British Columbia
shuaiwangvu
Dear Michael Simpson,
I am Shuai Wang and I am currently a PhD student of Computer Science in the Netherlands. I have read your paper titled Efficient Computation of Feedback Arc Set at Web-Scale. I have a few questions related to this paper and I’d really appreciate it if you may answer them.
1) For the probabilistic case of Berger-Shor algorithm, would we have the risk of having cycles after removing the FAS? Since all the arcs have a probabilistic chance of being removed, it is logical to suspect that there might be a case (even with low probability) where all the edges in a cycle are not removed.
2) I am dealing with weighted graphs rather than probabilistic graphs. I am not an expert on graph theory. Do you think I can develop a weighted case based on your greedy algorithm presented in section 5.1.1? Any advice is more than welcome!
3) I am not familiar with the Webgraph format. I followed your guidance on your github page for unweighted cases. But I’m not sure how to deal with weighted cases. Could you please give me a bit of guidance?
Thank you very much! Regards, Shuai Wang