Today’s catch

Every morning I go fishing in the arXiv. Or at least that’s the way I’ve been thinking about this daily ritual: I cast my net over the waters and look to see what strange and wonderful creatures I’ve brought up from the deeps. Today it hit me that I have the metaphor backwards. I’m the fish, and what’s going on here is that the arXiv dangles lures in front of me to see if I’ll take the bait. Some days I’m just not biting. Today, however, I was snapping at one hook after another. I’ll be the first to admit that I sometimes choose a brightly colored bit of fluff in preference to a nutritious worm. (Although I did pass on today’s proof that P ≠ NP—or was it the converse?)

Title: Laws of Graph Evolution: Densification and Shrinking Diameters
Authors: Jure Leskovec, Jon Kleinberg, Christos Faloutsos

How do real graphs evolve over time? What are “normal” growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time. Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log (log n))).

Title: Statistical Mechanics of Community Detection
Authors: Joerg Reichardt, Stefan Bornholdt

Starting from a general ansatz, we show how community detection can be interpreted as finding the ground state of an infinite range spin glass…. The community structure of the network is interpreted as the spin configuration that minimizes the energy of the spin glass with the spin states being the community indices. We elucidate the properties of the ground state configuration to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study. Further we show, how hierarchies and overlap in the community structure can be detected….

Title: Computer simulation of language competition by physicists
Authors: Christian Schulze, Dietrich Stauffer

… About every ten days a human language dies out, and in Brazil already more than half of the indigenous languages have vanished as a result of the European conquest. On the other hand, Latin has split in the last two millennia into several languages, from Portuguese to Romanian…. Thus similar to biology, also languages can become extinct or speciate into several daughter languages.

In contrast to biology, humans do not eat humans of other languages as regular food, and thus one does not have a complex ecosystem of predators eating prey as in biology. Instead, languages are meant for communication, and thus there is a tendency of only one language dominating in one region, like German in Germany etc. Will globalisation lead to all of us speaking one language in the distant future? For physics research, that situation has already arrived many years ago….

Thus in the history mankind we may have had first a rise, and later a decay, in the number of different languages spoken. In Papua New Guinea there are now 103 languages, each spoken by about 103 people; can this situation survive if television and mobile phones become more widespread there?

While we cannot answer these questions, we can at least simulate such ”survival of the fittest” among languages, in a way similar but not identical to biology….

Title: Trainspotting: Extraction and Analysis of Traffic and Topologies of Transportation Networks
Authors: Maciej Kurant, Patrick Thiran

The knowledge of real-life traffic pattern is crucial for good understanding and analysis of transportation systems. This data is quite rare. In this paper we propose an algorithm for extracting both the real physical topology and the network of traffic flows from timetables of public mass transportation systems.

Title: Sharp bounds for eigenvalues of triangles
Authors: B. Siudeja

The purpose of this paper is to prove the following theorem.

Theorem 1.1. Let T be a triangle in a plane of area A and perimeter L. Then the first eigenvalue λT of the Dirichlet Laplacian on T satisfies

\\frac{\\pi^2L^2}{16A^2} \\le \\lambda_T \\le \\frac{\\pi^2L^2}{9A^2}

The constants 9 and 16 are optimal.

Title: Quasicrystals: algebraic, combinatorial and geometrical aspects
Authors: Edita Pelantová, Zuzana Masáková

Voronoi tiling

Title: A Spinorial Formulation of the Maximum Clique Problem of a Graph
Authors: Marco Budinich, Paolo Budinich

In this paper we propose a new representation of the maximum clique problem in complex space. After a brief review of this famous NP-complete problem, we show how the adjacency matrix of a graph can be expressed as the square of a symmetric complex matrix. The vectors forming this matrix have zero length and Cartan has shown that this geometry can be treated elegantly with spinors…. We finish with a formulation of the maximum clique problem in this formalism and show that each graph uniquely identifies a spinor whose properties surely deserve deeper studies.

This entry was posted in mathematics, physics, science.

One Response to Today’s catch

  1. thomas cuny says:

    Paolo Budinich could discover the final theory if he understood
    that each fundamental particle in the universe has a spinor in common with
    every other fundamental particle in the universe.