I have a directed graph in which every node depicts a user and an edge between the user depicts that a mail has been exchanged between them. Weight of an edge shows the number of mails exchanged between the two users. I want to find the most weighted path from a node in this directed graph. I have used GEPHI to generate the attached graph. The graph is divided into different communities based on the weight of the edges. Each community is represented by a different color.
Hello Ankit,
How about this approach:
1. Set the "cost" of each edge equal to its negative weight. For instance, if between node i and node j you currently have 5 emails exchanged, set c_{ij} = -5.
2. At the node you are interested in starting, let's call it the root node, create an artificial commodity with a supply of 1 unit.
3. At the node you are interested in ending (or if you are interested in all other nodes, this piece will be embedded in a loop) create an artificial demand of 1 for the commodity created in step 2.
4. Solve a minimum cost network flow (MCNF) problem with the root node as the origin, your other node of interest as its destination and all other nodes acting as transshipment nodes (i.e. flow balance constraints at those nodes equal 0).
Even if you use a generic solver, due to the network structure, network simplex should perform much faster than a typical linear programming solver. Moreover, due to the total unimodularity of the constraint matrix, you're guaranteed to get an integer solution. This means that the unit of flow that needs to travel from origin to destination will not get split up along the way, so your solution will be of the form "use this edge/don't use this edge" for all edges in your graph.
Tthere are other graph optimization libraries (LEDA, Goblin, LEMON) which have even faster specialized MCNF algorithms implemented, so large scale problems should not be problematic.
Note: If you are familiar with network algorithms, you will recognize what I've just described in steps 1-4 as a simple tweak on the shortest-path problem. The tweak is to make all weights negative (which, typically, a specialized shortest-path algorithm like Dijkstra's can't handle but Bellman-Ford can), such that minimizing this negative total cost is equivalent to maximizing your total sum of weights.
Hello Ankit,
How about this approach:
1. Set the "cost" of each edge equal to its negative weight. For instance, if between node i and node j you currently have 5 emails exchanged, set c_{ij} = -5.
2. At the node you are interested in starting, let's call it the root node, create an artificial commodity with a supply of 1 unit.
3. At the node you are interested in ending (or if you are interested in all other nodes, this piece will be embedded in a loop) create an artificial demand of 1 for the commodity created in step 2.
4. Solve a minimum cost network flow (MCNF) problem with the root node as the origin, your other node of interest as its destination and all other nodes acting as transshipment nodes (i.e. flow balance constraints at those nodes equal 0).
Even if you use a generic solver, due to the network structure, network simplex should perform much faster than a typical linear programming solver. Moreover, due to the total unimodularity of the constraint matrix, you're guaranteed to get an integer solution. This means that the unit of flow that needs to travel from origin to destination will not get split up along the way, so your solution will be of the form "use this edge/don't use this edge" for all edges in your graph.
Tthere are other graph optimization libraries (LEDA, Goblin, LEMON) which have even faster specialized MCNF algorithms implemented, so large scale problems should not be problematic.
Note: If you are familiar with network algorithms, you will recognize what I've just described in steps 1-4 as a simple tweak on the shortest-path problem. The tweak is to make all weights negative (which, typically, a specialized shortest-path algorithm like Dijkstra's can't handle but Bellman-Ford can), such that minimizing this negative total cost is equivalent to maximizing your total sum of weights.
you can find appropriate ebook from
http://www.flazx.us/books/17462-Phylogenetic-Networks-Concepts-Algorithms-and-Applications/#.US2aPzA_vIU
A* for pathfinding. You have to properly set both h and f functions to match your interests. We used this for WSN routing approach at https://www.researchgate.net/publication/225161698_LECOMP_Low_Energy_COnsumption_Mesh_Protocol_in_WSN?ev=prf_pub
Hope this could be useful for you.
Best regards.
Chapter LECOMP: Low energy consumption mesh protocol in WSN
- Badges
- Science topic
- Similar topics
- Computer Science
- Data Mining