A space-dimension to the Web: a combinatorial optimisation problem
LudovicoVan
Published at: http://architectando.blogspot.com
/2009/07/space-dimension-to-web-combinatorial.html
Discussed at: (this thread)
How to give a *sensible* space-dimension to the Web.
Solutions, corrections, suggestions, etc. all very welcome.
This is an open project. Constributions will be acknowledged.
-LV
]
[
=== Setting:
Let G be a weighted, directed graph.
Let S be a lattice space for G.
Let M be a physical model for G.
Let U be (the absolute value of) the potential energy (in M over S,
given G)
=== Problems:
Problem 1 (optional): Express U.
Problem 2 (optional): Minimize U.
Problem 3: Express and minimize U, given the following constraints:
- Constraint 3.CG1: Weights in G have positive rational values.
- Constraint 3.CG2: Graph G is sparse.
- Constraint 3.CG3: Graph G is dynamic, i.e. nodes and edges change
(appear, desappear, change their weight). The dynamic is by discrete
singular events, changes are smooth.
- Constraint 3.CS1: S is a diophantine circle where positions start
from zero along the circumference, and the distance function 'x' is:
let c be the circumference (i.e. number of nodes in G)
let x' = x1 - x2 (absolute distance, integer >= 0)
x := x' , if x' <= c/2
c - x' , otherwise
(i.e. distance along the shortest arc, integer >= 0)
- Constraint 3.CM1: Within model M, the force 'F' is:
let i,j be non-negative integers indexing nodes in G
f_ij = k_ij * x_ij , if exists in G edge i->j with weight k_ij
0 , otherwise
(i.e. absolute elastic force, rational >= 0)
F = sum_i sum_j f_ij
(total force, rational >= 0)
- Constraint 3.CU1: Given that graph G is dynamic (see CG3), we want
to minimise U and keep it minimised!
=== Solutions:
My solution to Problem 3 at the moment consists in a "local approach".
I build a graph that is near-to-optimal (by inserting any new node at
a location so to minimise total energy change), plus have a process
that keeps iterating the solution space for local improvements (by
swap of adjacent nodes). The idea is that such process should be able
to keep up with changes (that are smooth, see 3.CG3 and 3.CU1), and
this together with said strategy of insertion should be enough to keep
the system at a near-to-optimal minimum (if not global! I guess this
depends on practical timing considerations... and complicated
calculations. Anyway, if needed, some simulated annealing might also
be implemented).
Incidentally, in the setting of Problem 3 there is no role for node
weights. This is a choice, not a simplification, related to semantic
considerations. It might be surely discussed: we are after a
*sensible* way to give a space-dimension to the Web.
]
LudovicoVan
Published at: http://architectando.blogspot.com
/2009/07/space-dimension-to-web-combinatorial.html
Discussed at: (this thread)
How to give a *sensible* space-dimension to the Web.
Solutions, corrections, suggestions, etc. all very welcome.
-LV
kunzmilan
Statistics of Web show lognormal distributions (truncated at one
connectivity). These distributions are known under different names for
information distributions (Lotka, Zipf, Bradford, Shockey).
Supposing that Web is oriented multigraph. its Laplace-Kirchhof matrix
has (n-1) nonzero eihenvalues.
kunzmilan
LudovicoVan
Sorry, I know zero of matrices, and can't see how that can help.
In any case, remember: we are given the graph, and we are given a an
energy function over some lattice; the problem is to minimise the
total energy of the system.
BTW, as far as semantics goes, to make the Web into a graph, we are
more interested into users navigation than crawling links: think Alexa
rather than a search engine.
-LV