8 views

Skip to first unread message

Jul 9, 2009, 7:49:01 PM7/9/09

to

[ "A space-dimension to the Web: a combinatorial optimisation problem"

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.

]

Jul 9, 2009, 7:51:11 PM7/9/09

to

[ "A space-dimension to the Web: a combinatorial optimisation problem"

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

Jul 11, 2009, 3:49:11 AM7/11/09

to

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

Jul 11, 2009, 10:30:33 PM7/11/09

to

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu