## Friday, January 21, 2011

### Building Junction Trees

Here's a 367 vertex Apollonian Network and its Junction Tree (aka Tree Decomposition)

A Junction Tree provides an efficient data structure to do exact probabilistic inference. In the context of traditional graph algorithms, it is known as the "Tree Decomposition". The amount of structure apparent from the junction tree shows that problems structured as Apollonian Networks have very low computational complexity.

The same junction tree structure can also be used to efficiently compute chromatic polynomials, find cliques, count self-avoiding walks, and the reason for this universality is that it essentially captures separation structure of the graph -- it is a representation of a complete set of vertex separators. In the Junction Tree above you can see 121 non-leaf nodes that separate the graph into 3 parts. Each node corresponds to a set of 4 vertices. There are also 363 edges, each corresponds to a set of 3 vertices that separates the graph into 2 parts. The fact that the graph can be recursively partitioned using small separators implies an efficient recursion scheme for problems on this graph.

I put together a Mathematica package to build Junction Trees like above using MinFill, MinCut and a few other heuristics. Some experimenting showed MinFill with Vertex Eccentricity for choosing between vertices with equal fill to work the best for general graphs, whereas MinCut worked the best for planar graphs.

Legendary Custom Homes said...

Hello there! I know this is kind of off topic but I was wondering which blog platform are you using for this site? I’m getting fed up of WordPress because I’ve had problems with hackers and I’m looking at options for another platform. I would be fantastic if you could point me in the direction of a good platform.
Tear down rebuild Cincinnati

remo said...

THANKS FOR THE INFORMATION...
<a href="http://www.chloros.in/digital-marketing-internship.htmlhttp://www.chloros.in/digital-marketing-internship.html>Digital Marketing Internship Program in Bangalore</a>

DedicatedHosting4u said...

Hey, very nice site. I came across this on Google, and I am stoked that I did. I will definitely be coming back here more often. Wish I could add to the conversation and bring a bit more to the table, but am just taking in as much info as I can at the moment. Thanks .

DedicatedHosting4u.com

MindtechAffiliates said...

Great. It is good to constantly coming up with creative ideas. Provides much needed knowledge. goal oriented blog posts and always tried to find creative ways to meet goals.

Thanks
Online affiliates

nagaqq said...

NAGAQQ | AGEN BANDARQ | BANDARQ ONLINE | ADUQ ONLINE | DOMINOQQ TERBAIK

Yang Merupakan Agen Bandarq, Domino 99, Dan Bandar Poker Online Terpercaya di asia hadir untuk anda semua dengan permainan permainan menarik dan bonus menarik untuk anda semua

Bonus yang diberikan NagaQQ :
* Bonus rollingan 0.5%,setiap senin di bagikannya
* Bonus Refferal 10% + 10%,seumur hidup
* Bonus Jackpot, yang dapat anda dapatkan dengan mudah
* Minimal Depo 15.000
* Minimal WD 20.000

Memegang Gelar atau title sebagai AGEN BANDARQ Terbaik di masanya

Games Yang di Hadirkan NagaQQ :
* Poker Online
* BandarQ
* Domino99
* Bandar Poker
* Bandar66(NEW GAMES)

Info Lebih lanjut Kunjungi :
Website : NAGAQQ
WHATSAPP : +855967014811
Line : Cs_nagaQQ
TELEGRAM :+855967014811

BACA JUGA BLOGSPORT KAMI YANG LAIN:
berita nagaqq/
agen bandarq online/
Kemenangan NagaQQ/

Yasmin Akter said...
john said...
Unknown said...
John said...

مهدی احمدوند
راغب
مهدی جهانی
دانلود آهنگ جدید ایوان بند

periyannan said...

Thanks for such a great blog here. I was searching for something like this for quite a long time and at last, I’ve found it on your blog. It was definitely interesting for me to read about their market situation nowadays.

python internship | web development internship |internship for mechanical engineering students |mechanical engineering internships |java training in chennai |internship for 1st year engineering students |online internships for cse students |online internship for engineering students |internship for ece students |data science internships

Jeffrey Collins said...

Experts and professionals of BookMyEssay who have access to the appropriate educational materials are well-educated and qualified. They are offering the quality 100% Plagiarism Free Essay Help to the students who are burdened with their assignments.

Alteryx Training in Chennai said...