Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
107 views
in Technique[技术] by (71.8m points)

What's the best algorithm for extracting all unique, complete subgraphs from an undirected graph of perhaps 1,024 nodes?

I ask this question with apologies for my obvious mathematical shortcomings as a practical programmer. It's been more than 40 years since I did well in high-school algebra and then failed at anything higher. The concept of "NP-complete" and "NP-hard" problems has been difficult to grasp, but I've tried. I even bought and studied what appears to be the original guide to this class of problems, Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson.

https://goodreads.com/book/show/284369.Computers_and_Intractability/

Be that it may. It is to be hoped the question itself is clear enough. What's the best publicly available brute-force algorithm (with efficient branch pruning) thus far for the specific problem of extracting all unique, complete subgraphs (within which all distinct nodes (vertices) are connected to each other (over unique edges)) from any random undirected graph? That is to say, the algorithm should be able to first extract the largest unique, complete subgraphs, however many there might be, and then in that order extract all smaller unique, complete subgraphs that are (by definition, I think) not encompassed by any larger unique, complete subgraphs, thus avoiding the duplicative production of non-unique (implied) results.

Ouch, trying to spell it out in clear English like that makes my head hurt a bit. It is to be hoped that this description is nonetheless straightforward enough. A standard C/C++/(or even Python) library to provide this functionality with reasonable computational resources such as a Ryzen 5 3600 box with 64GB/128GB of DRAM would be great, especially if a complete analysis thereof with 1,024 nodes could be finished within a day or two, but I'll take what I can get with many thanks.

And if there's a FAQ or essay somewhere on the Web that covers this topic in English that can be understood by a non-mathematician, then that'd be even better!

Edit: The language in the following paper is admittedly a little over my head, but for you computational mathematicians out there, can you confirm that it does in fact substantially address the core problem itself? If so, I can begin a heroic effort to understand this "Bron–Kerbosch" algorithm with faith that it's the correct track to follow. -_-

"The worst-case time complexity for generating all maximal cliques and computational experiments" by Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi

(The University of Electro-Communications, Department of Information and Communication Engineering, Chofugaoka 1-5-1, Chofu, Tokyo 182-8585, Japan) (Toyota Techno Service Corporation, Imae 1-21, Hanamotocho, Toyota, Aichi 470–0334, Japan)

https://snap.stanford.edu/class/cs224w-readings/tomita06cliques.pdf

question from:https://stackoverflow.com/questions/65930812/whats-the-best-algorithm-for-extracting-all-unique-complete-subgraphs-from-an

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Yes, Bron--Kerbosch is what you want. There's an implementation in NetworkX, some readable pseudocode on Wikipedia if you know your set operators, and a Python implementation by yours truly and many more discoverable by searching.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...