A semantic space-dimension for the Web

[ "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: http://groups.google.co.uk
                /group/sci.math/browse_frm/thread/2cd2380c0bd245eb
  
  How to give a *sensible* space-dimension to the Web.
  Solutions, corrections, suggestions, etc. all very welcome.
  This is an open project. Contributions 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.
 
]