I need a partitioning algorithm for a direct weighted graph. I have seen that most of the algorithms are supported to indirect and indirect weighted graphs. So please give me information regarding direct weighted graph partitioning which can also be support for a large graph. If possible provide me a links to that topics and examples on that.
Hi Muttipati, there is a method using 'Graph spectra partitioning.' The idea is to calculate the eigenvectors and eigenvalues from the Adjacency matrix. I used it for directed graphs - complex weighted (using complex numbers as weights), so the Adjacency matrix was an Hermitian matrix. However your case must be a little bit simpler.
Hi Jose Dolz. thanking you for givin a useful information
If possible, can you state how you want the graph partitioned? Are you maximizing say the weighted cost of the partitions? Minimizing their cost? Maximizing number of vertices in the partitions? Depending on what objective you have, the problem may be easier or harder.
You can use Cross-Entropy method for discrete (Combinatorial) Optimization. See, for example, article (with Example: Max-Cut Problem) :
Cross-Entropy Method // Encyclopedia of Operations Research and Management Sciences, Third edition, 2012. http://www.maths.uq.edu.au/~kroese/ps/CEEncycl.pdf
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs