Exploring Cliques and Clique Problems
Вставка
- Опубліковано 28 бер 2020
- In this video we'll explore a collection of interesting problems, collectively involving the concept of Cliques. A clique is a collection of nodes which are all connected together. For example, in FaceBook, a collection of people who are all friends with each other. It is fascinating to explore Cliques because they represent some of the simplest forms of the P vs NP problem.
Source code is not yet available. I will update this description when it is uploaded. Thanks for watching all!
Support What's a Creel? on Patreon:
/ whatsacreel
FaceBook:
/ whatsacreel
Music Channel:
/ @creelsmusic5814
Another channel with random things:
/ @ftlol6091
Software used to make this vid:
Visual Studio 2019 Community:
www.visualstudio.com/downloads/
OBS:
obsproject.com/
Davinci Resolve 16:
www.blackmagicdesign.com/prod...
OpenOffice:
www.openoffice.org/
Creel, your one of the sharpest programmers I have ever come across, love your vids
Cheers mate! So great to hear, thanks for watching :)
Just wanted to share that I was given this problem as a freshman in computer science in a computational genetic algorithms class which offers a kind of solution.
The idea is that you can start with many random groups of friends and these groups are considered genomes like in biology. Next whichever groups have the most connections will be considered the most fit and can " breed " with one another. The selection for breeding is random but biased towards more fit genomes and each genome also has a chance to mutate which swaps in other nodes randomly. The algorithm would work by first looking for a clique of size 2 and then move up in size as it found more cliques.
Because of the nature of genetic algorithms there is no solution guaranteed, but in practice I was able to find the max cliques in graphs that were 100 by 100 or larger in a few seconds most of the time with only semi optimized C++ code. These kinds of computational genetic algorithms are used in many NP hard problems to offer a timely estimate at the best solutions. You trade the mathematical guarentee for speed but they also usually give a fairly good solution if not the max. One other good thing is the algorithm can keep running for as long as you would like to find improved solutions so the quality of the solution is somewhat based on how long the algorithms is run.
"Click" problem solved , first to 'clique" in your video ! , btw thanks for all ASM tutorials very useful and well presented , i made some optimization with that for my daily work , thanks !
Haha! Cheers for watching mate!! Sooo great to hear when folks find these humble offerings useful :)
Alright Creel and The Creel Clique!... I'm not a mathematician but this vid reminded me of a graph problem (hopefully/maybe) related to the 4 colour map theorem, perhaps even a simpler proof, you may be able to help confirm/deny.
--
In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.
--
The maximum number of nodes with non-overlapping each-to-every connectors is 4 in a 2D network graph, same as the 2D map theorem minimum.. I know one's a minimum, one's a maximum, but they * seem * related conceptually.. two views of the same problem? It's the same in 1D (2 colours/nodes) and arguably iin 3D (infinite - or only limited by physical size of nodes/connectors and regions/light wave length)
I wanted to share an optimization I came up with for the first 4-clique problem you presented. If a node is in a 4-clique, then it must be connected to the other 3 nodes in the 4-clique, which means it must have at least 3 connections to other nodes, so any nodes with 1 or 2 connections (not counting reflexive connections) can be pruned from the search. This lets you ignore nodes B, E, F, and I, and if you remove those nodes and their edges and apply this optimization recursively you get rid of G and J as well, so you are left with a graph containing only the nodes A, C, D, and H, so there's only 1 case to check. A similar technique can be used to determine the largest clique that might conceivably exist by counting edges per node, since an N-clique must have N nodes with N-1 edges or more each, and the given graph happens to have 5 nodes with 4 or more edges (A, C, D, G, and J). If you prune for that case, though, you end up deleting every node, so therefore a 5-clique does not exist in this graph.
This doesn't solve the problem entirely (in fact, it performs rather poorly on your following, highly-interconnected example), but it would be a much better algorithm than brute force in most cases, especially since you can prune more aggressively as you go on without having to start over entirely (for example, by only pruning nodes with 1 edge and then checking if you have a 3-clique, then checking if a 4-clique is possible with the current graph, then pruning nodes with 2 or fewer edges and checking that). Other optimizations that come to mind for this are A. if a node with exactly N-1 nonreflexive edges has any pair of nodes it's connected to that do not themselves share an edge, that node cannot be a member of an N-clique and may be pruned, and B. if pruning for an N-clique deletes every node and proves that an N-clique does not exist, no larger cliques can exist, which automatically gives you a new upper bound.
footnote: after a fair amount of working out by hand, the largest possible clique in your highly-interconnected example, by this method, is a 4-clique (of which BCDJ is an example). Looking forward to the release of your Clique Explorer program, and hoping it has the ability to delete or hide columns from a generated grid so I can more extensively try my method.
Just get the maximum number of friend anyone has on Facebook (0(n) problem). Then hire the same number of person to form a clique on Facebook. Then you'd have found the maximum clique on Facebook ;-)
Now THAT is a brute force approach.
It seems very likely that the problem will always remain exponential, but I can see some ways to reduce it.
Given the number of friend each person has (including themselves), start at the highest number, K:
Are there K people with K or more friends? If yes, then search only people with K or more friends for cliques of exactly K. If you haven't found any K-cliques, decrement K and start again at the beginning of this paragraph.
Both the limit to searching among K people and the limit to searching for cliques of exactly K reduce the complexity at each stage, thus you will find all largest maximal clique more quickly. Altho still exponential, it will in general be a smaller exponential.
Brilliant
Very cool video.
Cheers mate, thanks for watching :)
For much larger node sets with sparse edge sets, there is some pretty cool stuff in homology to help you deal with this question better than brute force checking all cliques. Not sure what the computational complexity of computing flag complex homology is, but it can tell you all kinds of cool things about a network
this reminds me of the school presentation I made about maximum clique algorithm for my data algorithm class, I already forgot what I learned back then
Not the whole world! Some people are still holding out against facebook.
but what is the most likely biggest cliques in youtube given the number of people and average friends count
Hello, first of all thank you for your videos. Can you do a tutorial for SSE using an array an get the max value, I need to do a work for university using SSE with asm in c++ and my teacher can't explain me anything, so I was searching for tutorials and I saw your channel, you explain very good. Thank you for all 💪🏻.
That's a great suggestion mate! What data types are you using? Are the they ints? Or floating point?
Also, apologies I didn't respond. For some reason, I was not notified about your comment...?? Well, I'm glad I saw it now. Thanks for watching :)
hey, I wrote on one of your vids that I had a problem with malloc in masm, well, I've researched further.
you need to use INCLUDE and INCLUDELIB to include libs in your masm code but I have no Idea which files I should include to use malloc and the difference between include and includelib are still a bit confusing, can you please explain?
Not sure mate. I am able to call it without trouble here. Just "extern malloc: proc" and then "call malloc".
You do have to link with the library that defines it, yes, but Visual Studio links with those standard windows libraries automatically. You can turn that off in the project settings. Anyway, I am not sure what the trouble is mate. Are you using Linux or another compiler?
@@WhatsACreel I am using the standard masm compiler that comes with vs2019, litterally have just selected "new console application", added the masm build dependency and set the item's build action to microsoft macro assembler.
p.s. I'm using windows.
Hello there, thanks for your effort, it is very great and helpful video can you please upload the source code, it will be great.
Interesting. I've been working on an algorithm to orient a graph which is somewhere inclusively between polynomial and factorial time (as part of a problem for understanding limitations of neural nets like the 'XOR problem' as well as for better understanding multi-input Boolean functions). Anyways, if I just reverse the ordering sequence on the matrix (so that it grows from small Ls to larger Ls making larger squares), maybe I could find an algorithm for finding the largest maximal clique.
Hi, maybe you can help confirm or deny this graph problem (hopefully/maybe) related to the 4 colour map theorem, and perhaps the basis for a simpler proof..
--
In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.
--
The maximum number of nodes with non-overlapping each-to-every connectors is 4 in a 2D network graph, same as the 2D map theorem minimum.. I know one's a minimum, one's a maximum, but they * seem * related conceptually.. two views of the same problem? It's the same in 1D (2 colours/nodes) and arguably iin 3D (infinite - or only limited by physical size of nodes/connectors and regions/light wave length)
@@PrivateSi Very interesting too. I almost completed the algorithm I mentioned above but got tied up with helping someone who lost their job due to COVID. But, I have been reviewing it lately. They seem possibly related, but I will keep this in mind over the next few months.
What if we use SVD to vectorize nodes, cluster them, then brute force whithin each cluster?
That would work, though there are several, faster iterative optimization techniques for optimizing for the maximal clique (linear programming ones).
people who gave money have always friends 😁
There is a p time solution to this.
Please use my background music in your video i need support 🙏