helped needed for weighted graphs and input format

[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

[stamps]

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 ***@***.***> 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 <#2>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AARMSRIEHAI4LU2UDD34BMDR67D2TANCNFSM4PUFJYCQ> .

-- Michael Simpson Postdoctoral Researcher University of British Columbia

[shuaiwangvu]

Dear Michael,

Thanks very much for your reply and I will update my code accordingly.

However, I can't find any useful tutorial about adding weights to edgelist (and convert it to the WebGraph format). Do you still remember how you did it when you were evaluating those data you used in your paper (shall I simply append the weights to each entry of the edgelist file, or maybe I need an additional file)?

The current unweighted case is

1. obtain webgraph file : java -cp "lib/*" it.unimi.dsi.webgraph.BVGraph -1 -g ArcListASCIIGraph dummy filename
2. compute the offset: java -cp "lib/*" it.unimi.dsi.webgraph.BVGraph -o -O -L filename

Also, who should I contact if we'd like to publish our data so other people can use it for research of their algorithms (especially for the weighted scenarios)?

Thank you very much!

[stamps]

Hi Shuai, Apologies for the delayed reply. I was able to track down the weighted versions of the code. They simply use a different webgraph graph class: "ArcLabelledImmutableGraph". I've attached the weighted FAS algorithm based on a simple DFS to illustrate how the arc labelled graph is loaded and used. I also attached the script I have for generating the arc labelled graphs from an unlabelled ImmutableGraph. Once you have generated a weighted arc list, you would need to store the resulting graph in the webgraph format. I believe I followed the instructions under the heading "Importing your labelled data" at this link <https://javadoc.io/doc/it.unimi.dsi/webgraph/latest/index.html>. Hopefully they answer the question of how to handle weighted graphs for you. Best, Michael

…

On Tue, Aug 18, 2020 at 12:17 PM Shuai Wang ***@***.***> wrote: Closed #2 <#2>. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AARMSRN2HL36543TADUDAKTSBLHVBANCNFSM4PUFJYCQ> .

-- Michael Simpson Postdoctoral Researcher University of British Columbia