Random graphs (2/4)

This is the next generation of Random graphs (1/4). Surprisingly, isn’t it?…: 2/4 after 1/4, is something like descovering together upper bounds of mankind… Personal remark: keep doing good job and follow links in this small delirium therefore my hitting indexes will increase and I will be happy, feeling love all around…

Graphs taken into account are produced following specs from [5], [6]. Needed randomness come from results like [5], Theorem 1 (maybe some more extensions would be welcomed, but it is good enough for the moment) and also from philosophy behind pseudo-random generators (see for instance [7], Pseudo – Numbers chapter).

So, which is the plan…? This one remembers me about the several vultures hanging over a branch, in golden Jungle books movie, asking each other What you wanna do, what you wanna do..?.

Let notice first of all that entropy itself is exactly a mathematical estimator for function u(x) = -log(p(x)):

where X is a random variable and E denotes mathematical expectation for function u. Herein, p denotes a probability density function over X. Note that base 2 of the logarithm is not very significant. However, because it sounds more gorgeous to have bit(s) as unit(s) to whatever measure, we can agree on this particular base.

Hence, according with Shannon, it should be the average information got when unleash a random experiment to produce itself inside a graph, along its edges or inside its nodes. This is why it is very important that the random background to be achieved: whatever we would like to measure inside the graph as information entropy, it has to reflect a random process developed inside the graph. It is out of reason to talk about whatever kind of information sample inside a static structure. This is why Dehmer papers [1],[2],[3] are actually retarded language from a dying species: they not reflect (or at least don’t sustain) a dynamic process. To reflect the structure of a graph through entropy in the lacking of defining a process is the same with making love with a ghost.
Therefore, point is: what process can be defined as a natural prolong of a definition of a graph?
I feel you suspect me that I know the answer. You feel I suspect you that you don’t think that… A very complex world…
Anyway, is time to go to work. I hate this, also today. Hope you believe me.

Bibliography
[5] On Generating Random Network Structures: Trees Alexy S. Rodionov, Hyuseung Choo – P.M.A. Sloot et al. (Eds.): ICCS 2003, LNCS 2658,pp 879-887, 2003 © Springer-Verlag Berlin Heidelberg 2003
[6] Generating Random Trees and Connected Graphs (posted by a usefull guy called Juan Antonio)
[7] Introduction to Statistics Ewa Paszek

…see also this nice approach:
Random Graphs: The Basic Models – Sarvagya Upadhyay

Copyright ©2009 Marius Iancu (http://marius09.wordpress.com)

		Update (March 06) I discovered use of LaTeX inside wordpress, therefore I played a little with it (I mean with LaTeX..) and, suddenly, some minor changes occured, comparatively to the original text. If you really miss the original text, just notify me and I will try to send you a diploma and, of course, a medal. Here bellow are some great links one mab’lord (math blogger in wordpress – following StarWars nice way of naming stuff) would use: Symbols http://omega.albany.edu:8008/Symbols.html Commands http://www.artofproblemsolving.com/LaTeX/ AoPS_L_GuideCommands.php WordPress ref. http://support.wordpress.com/latex/

Random graphs (1/4)

These days i tryed to figure out several issues on defining entropy/information measures on graphs. (it happens from time to time, to deeply think on humanity problems; result is a very proud and noisy sleep – neighbours allways know that I deal with some fundamentals stuff).

There are several approaches that seem very artificial to me (Dehmer [1],[2],[3] and maybe more than those…). This is still not very tragically, due to the fact that many things are even more artificially…
Problem in defining entropy in terms of different metrics in a graph, and afterwards claim hundreds of relations between hundreds of quantities is simply garbage, in my opinion…. unless of a basic check of the meaning of defined quantities…
Why not, for instance, to define as entropy in a connected graph G=(V,E) something like:
(*) Entropy(G) = sum{d(v1)*sqrt( ln(max(d(v2)),l(v1,v2)))], sum performed for all edges (v1,v2) from E ; d(x) is the degree of vertex x ; sqrt is squared value ; l(v1,v2) = the longest path of distinct vertexes between v1 and v2 (…not to many maths symbols allowed here – but anyway, ideas are more or less important). …I bet that one can produce at least 10 interesting inequalities related to (*), based on |V|, |E| and, maybe, on the number of words Jay Leno said last Saturday night…
Issue is that a very strong concept – like entropy – has to be carefully integrated with graphs structure and metrics. From my point of view, [3] is the perfect example of an useless and hopeless approach. We can produce 100000000000 similar results, starting with different “functionals of information” (…yeah!, bad luck, don’t mention it again…).

So, what can be done? – I don’t know, but let try something statistically. Maybe a Monte Carlo algorithm applied for a random graph, maybe verifying statistical hypothesis (as the distribution over vertex space) – anything… What and who (excepting authors like Mr. Dehmer) could certify that a certain measure measures what it suppose to measure? Uncertaintity of a graph structure…for instance…? What is uncertainty of a graph? I think the original Shannon[4] meaning of signal propagation should be maintained unless serious work would reveal a new significance.
Seems obviously that any start should be done inside random graphs area – randomness seem to be the natural background to whatever information measure we would like to suggest/check/publish/become rich/buy an island in Bahamas/get cars, women and more cars…./get Nobel/ more islands/ more cars…

Just for fun, here bellow are some random graphs. All generated in .NET following some algorithms I will talk about in next post. Yes, I did the programming and I proudly share the code with anybody excepting Mr. Dehmer…. Anyway, something nice coming from these Dehmer papers: I like the draws and metaphors behind j-Spheres definitions…. Is something like: someone publishes in front of his article that instead of “cow” that he will use something like “delta-vertebrate-muuuuu! based”… why? no one knows… but it still sounds funny: “j-Spheres”… wow! it remind me by Star-Treck, with a very retarded captain Picard comitting suicide because of claustrophobia…
Therefore, here bellow are some beautifull random connected graphs generated by what I will call j-NET app….. (seriously, I like the j-metaphor…):

…some zoom-in is welcomed, I suppose:

And finally, some j-something (for a 50-vertex graph, having 100 random generated edges):

..I will be back on the algorithm of random generating graphs, it is very important to have a mathematical support for the “random” word, in order to approach the spirit of Shannon theory…
Referrences (unbelievable!, I am proud of me!)
[1]
Information processing in complex networks:
Graph entropy and information functionals – Matthias Dehmer
[2]
New Topological Information Indices Based on the Full Neighborhood of All Atoms – Matthias Dehmer & colab.
[3] Entropy Bounds for Hierarchical Molecular Networks- Matthias Dehmer & colab.
[4] A Mathematical Theory of Communication – Claude Shannon

Copyright ©2009 Marius Iancu (http://marius09.wordpress.com)
yep! yep! yep!