How to calculate the fractal dimension of a complex network: the box covering algorithm
Comments: 16 pages, 14 figures
Subj-class: Disordered Systems and Neural Networks; Statistical Mechanics
Covering a network with the minimum possible number of boxes can reveal interesting features for the network structure, especially in terms of self-similar or fractal characteristics. Considerable attention has been recently devoted to this problem, with the finding that many real networks are self-similar fractals. Here we present, compare and study in detail a number of algorithms that we have used in previous papers towards this goal. We show that this problem can be mapped to the well-known graph coloring problem and then we simply can apply well-established algorithms. This seems to be the most efficient method, but we also present two other algorithms based on burning which provide a number of other benefits. We argue that the presented algorithms provide a solution close to optimal and that another algorithm that can significantly improve this result in an efficient way does not exist. We offer to anyone that finds such a method to cover his/her expenses for a 1-week trip to our lab in New York (details in this http URL).
Para ler depois:
Paradoxes of Randomness
Authors: G. J. Chaitin (IBM Research)
Subj-class: History and Overview; Logic
I'll discuss how Goedel's paradox "This statement is false/unprovable" yields his famous result on the limits of axiomatic reasoning. I'll contrast that with my work, which is based on the paradox of "The first uninteresting positive whole number", which is itself a rather interesting number, since it is precisely the first uninteresting number. This leads to my first result on the limits of axiomatic reasoning, namely that most numbers are uninteresting or random, but we can never be sure, we can never prove it, in individual cases. And these ideas culminate in my discovery that some mathematical facts are true for no reason, they are true by accident, or at random. In other words, God not only plays dice in physics, but even in pure mathematics, in logic, in the world of pure reason. Sometimes mathematical truth is completely random and has no structure or pattern that we will ever be able to understand. It is NOT the case that simple clear questions have simple clear answers, not even in the world of pure ideas, and much less so in the messy real world of everyday life.
Concerning Dice and Divinity
Comments: Contribution to proceedings of Foundations of Probability and Physics, Vaxjo, 2006
Einstein initially objected to the probabilistic aspect of quantum mechanics - the idea that God is playing at dice. Later he changed his ground, and focussed instead on the point that the Copenhagen Interpretation leads to what Einstein saw as the abandonment of physical realism. We argue here that Einstein's initial intuition was perfectly sound, and that it is precisely the fact that quantum mechanics is a fundamentally probabilistic theory which is at the root of all the controversies regarding its interpretation. Probability is an intrinsically logical concept. This means that the quantum state has an essentially logical significance. It is extremely difficult to reconcile that fact with Einstein's belief, that it is the task of physics to give us a vision of the world apprehended sub specie aeternitatis. Quantum mechanics thus presents us with a simple choice: either to follow Einstein in looking for a theory which is not probabilistic at the fundamental level, or else to accept that physics does not in fact put us in the position of God looking down on things from above. There is a widespread fear that the latter alternative must inevitably lead to a greatly impoverished, positivistic view of physical theory. It appears to us, however, that the truth is just the opposite. The Einsteinian vision is much less attractive than it seems at first sight. In particular, it is closely connected with philosophical reductionism.
How Does God Play Dice? (Pre-)Determinism at the Planck Scale
Authors: Gerard 't Hooft (Utrecht)
Comments: An Essay in honour of John S. Bell. 8 pages TeX, no figuresReport-no: SPIN-2001/09 / ITP-UU-01/15
In deterministic theories, one can start from a set of ontological states to formulate the dynamical laws, but these may not be directly observable. Observable are only equivalence classes of states, and these will span a basis of "beables", to be promoted to an orthonormal basis of Hilbert Space. After transforming this basis to a more conventional basis, a theory may result that is fundamentally quantum mechanical. It is conjectured that the quantum laws of the real world may be understood from exactly such a procedure.