Hi, I am Cezary, a student of computer science at the Cybernetics Faculty, Military University of Technology, Warsaw. I am interested in developing the BGL. I've got an idea related to the Topology Generators. I have participated in a project concerning epidemics spreading and, as a part of the project, we have implemented several social networks generators (Barabási–Albert model for instance). I hit upon an idea to implement these algorithms apart from proposed topology generators. I know that Boost.Graph contains some algorithms for generating networks, I would like to add some extensions: 1. There is Erdős-Rényi model generator in two versions G(n, p) and G(n, m). I think I could provide some additional implementations for specific cases, I mean: a) Fast generator of sparse graphs inspired by http://www.inf.uni-konstanz.de/algo/publications/bb-eglrn-05.pdf. b) Fast generator of dense graphs, algorithm by Keith M. Briggs Mar 31, 2006 (the only implementation of this one I've seen in NetworkX library). 2. There is only Beta-model generator of Small World network in the library. I would like to add Alfa-model generator as well as Kleinberg model generator. Here are some interesting materials: http://tam.cornell.edu/tam/cms/manage/upload/SS_nature_smallworld.pdf http://www.bsos.umd.edu/socy/alan/stats/network-grad/summaries/Watts-Six%20D... http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.381&rep=rep1&type=pdf 3. At the moment we've got only PLOD algorithm to generate ScaleFree networks. I could provide other ones: a) Basic generator often seen in popular libraries, for instance NetworkX. b) Generalized generator with probabilities of adding new edges and rewiring existing ones. c) Simplified models generators: A (uniform attachment) and B (no growth). Coming back to Topology Generators I would implement them for some "basic" topologies, let's say: path, star, cycle, wheel, ladder, grid, hypercube, barbell, complete, frucht and many others if time remains... I would be glad to know your opinion. Best, Cezary
Hi Cezary, I've got an idea related to the Topology Generators. I have participated in
a project concerning epidemics spreading and, as a part of the project, we have implemented several social networks generators (Barabási–Albert model for instance). I hit upon an idea to implement these algorithms apart from proposed topology generators.
I think that this is a nice complement to work I did a couple of years ago. I would certainly like to see the BGL usable for social network analysis.
I know that Boost.Graph contains some algorithms for generating networks, I would like to add some extensions:
In fact, some of the generators that you mentioned. Erdos-Renyi, PLOD. However, I'm not a huge fan of their interfaces. I'm not sure why there was a need to build them as iterators. How do you think you could improve their interfaces. For the record, the two Erdos-Renyi generators are actually equivalent. There's a relatively simple mathematical correspondence, but I forget what it is :) They should generate graphs with the same basic measures.
Coming back to Topology Generators I would implement them for some "basic" topologies, let's say: path, star, cycle, wheel, ladder, grid, hypercube, barbell, complete, frucht and many others if time remains...
I would be glad to know your opinion.
The "easy" ones :) I did some very preliminary work on these also. Did you have any thoughts on how you might implement these? How might you specify, for example, which vertex represented the center of a star graph? Andrew Sutton andrew.n.sutton@gmail.com
In fact, some of the generators that you mentioned. Erdos-Renyi, PLOD. However, I'm not a huge fan of their interfaces. I'm not sure why there was a need to build them as iterators. How do you think you could improve their interfaces.
I think they should have got non-iterator versions. It's worth pointing out that we would like to have got a possibility of inducing generators on an existing set of vertices. I think it could be less comfortable with iterators than with functions like the existing *generate_random_graph*. So, there are two options we could call generators - the first in which we have got an empty graph on input and we have to indicate a count of vertices to generate (or probability, it depends on algorithms), the second we have got a graph with some set of vertices and we would like to add some edges. There is also the third option, when we have got a graph with some set of vertices and some set of edges. Unfortunately I think there is no good solution of how the generators should behave in such situation. Let's assume that someone wants to induce a path topology on a star graph. It's impossible when we don't admit rewiring and/or removing any edges. I know this example is nonsensical, but illustrates the problem. Users may expect the algorithm to not modify their graph beyond the addition of edges. Taking this into consideration I'm coming to a conclusion that we should let users induce topologies only on graphs without edges. Or, to be more precise, if some graph has got edges we shouldn't be concerned about them and return a new graph with a set of vertices from the input graph and only generated edges. For the record, the two Erdos-Renyi generators are actually equivalent.
There's a relatively simple mathematical correspondence, but I forget what it is :) They should generate graphs with the same basic measures.
Well, that's true ;) By the way - I think this is a good idea to provide a few algorithms for sparse and dense graphs apart from the existing generators. They differ in complexity. The "easy" ones :) I did some very preliminary work on these also. Did you
have any thoughts on how you might implement these? How might you specify, for example, which vertex represented the center of a star graph?
For empty graphs it could be randomly chosen. For graphs on which we induce topologies we could let a potential user choose it at random or to point the concrete one out. The same concerns wheel graphs etc... As for functions like *is_star*, *is_path*, *is_wheel* etc. I think we can treat them as particular cases of *graphs' similarity* problem. At the moment I am not able to point "ready-made" algorithms out. But I'll look for them. As to functions like *is_smallworld*, *is_scalefree*, *is_erdosrenyi *I think this is sufficient to count measures like *clustering coefficient* for instance. I'm curious to see your comments, suggestions. I look forward to hearing from you. On 24 March 2010 14:35, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
Hi Cezary,
I've got an idea related to the Topology Generators. I have participated in
a project concerning epidemics spreading and, as a part of the project, we have implemented several social networks generators (Barabási–Albert model for instance). I hit upon an idea to implement these algorithms apart from proposed topology generators.
I think that this is a nice complement to work I did a couple of years ago. I would certainly like to see the BGL usable for social network analysis.
I know that Boost.Graph contains some algorithms for generating networks, I would like to add some extensions:
In fact, some of the generators that you mentioned. Erdos-Renyi, PLOD. However, I'm not a huge fan of their interfaces. I'm not sure why there was a need to build them as iterators. How do you think you could improve their interfaces.
For the record, the two Erdos-Renyi generators are actually equivalent. There's a relatively simple mathematical correspondence, but I forget what it is :) They should generate graphs with the same basic measures.
Coming back to Topology Generators I would implement them for some "basic" topologies, let's say: path, star, cycle, wheel, ladder, grid, hypercube, barbell, complete, frucht and many others if time remains...
I would be glad to know your opinion.
The "easy" ones :) I did some very preliminary work on these also. Did you have any thoughts on how you might implement these? How might you specify, for example, which vertex represented the center of a star graph?
Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (2)
-
Andrew Sutton -
Cezary Bartosiak