|
|
| (4 intermediate revisions by the same user not shown) |
| Line 3: |
Line 3: |
| == Project Members == | | == Project Members == |
|
| |
|
| | * Adam Campbell |
| | * Laura Feeney |
| | * Orion Penner |
| | * Meritxell Vinyals |
| | |
| | Join us if you are interested in the proposal below!!! |
|
| |
|
| == Project Proposal == | | == Project Proposal == |
|
| |
|
| Simon Herbert [5] discusses a broad ranging set of systems (business, biological
| | [[Media:project_proposal.pdf | project_proposal.pdf]] |
| . . . ) that exhibits were what he calls ’nearly descomposable systems’. Simon
| |
| suggests that interactions between modules in such systems are weak and that
| |
| the subsystems behave nearly independently. These inter-module interactions
| |
| are somehow less important or occur in less frequency than intra-module inter-
| |
| actions. However these descomposition of the system may degradate its solution
| |
| substantially. Therefore there are several works in the literature that have stud-
| |
| ied what is the optimal way of clustering a system into modules that behave
| |
| indepedently of each other and that minimize the degradation of the system.
| |
| This idea could be applied to hard optimization problems. Common optimiza-
| |
| tion procedures seek to improve performance of the system as a whole. However
| |
| in the case of hard optimization problems due to the complexity of the problem
| |
| (usually NP-problems) this approach is not very succesful.
| |
| Hence modularization can be seen as an objective way to simplify the prob-
| |
| lem to be solved. The problem itself changes as a result, and the new problem
| |
| that we obtain is computationally simpler. To modularize a problem it has to
| |
| be structurally modular. Thus, it must exist some descomposition of this sys-
| |
| tem such that it has stronger (more numerous) intra-module dependencies than
| |
| inter-dependencies between modules.
| |
| However the degradation of the system will also depen on the importance
| |
| of this remaining inter-dependencies between modules [6]. Thus, if the system
| |
| is structurally and functionally modular then if we cluster it into modules that
| |
| behave independently of each other the overall solution/behaviour will be no far
| |
| from the optimal. However if this system has a strong inter-dependencies among
| |
| modules then this approach gives as a result solutions that are deeply affected.
| |
| A strong inter-dependency among modules is defined as one the stability of a
| |
| given configuration of one or both modules is sensitive to the attractor module
| |
| and this configuration which is most stable may also differ. In other words, we
| |
| have to check if modules attractors are affected or unaffected by state changes
| |
| in another module.
| |
| From the above introduction, we can formulate an approach to the problem
| |
| in tree steps: 1) Finding the best hierarchical modularity or simple modularity
| |
| that fits on the complexity and on the underlying network; 2) in case of a hierar-
| |
| chy, define the organization or how to deal with the inter-module dependencies;
| |
| and 3) finding a strategy of search within the given submodule.
| |
| Our approach:
| |
| • Use as a framework of analysis for the nearly-descomposable systems the
| |
| Stuart Kauffmans model of fitness landscapes. Discuss if the model is
| |
| enough general and suitable for the problem, if we can visualize the solu-
| |
| tions somehow, how implement it.
| |
| • Study if already existing algorithms to create a simple modularitzation [4]
| |
| [3] [2] or a hierarchical modularitzation [1] of the network only tested in
| |
| data mining for biological or social networks apply to these optimization
| |
| systems
| |
| • Study in case of hierarchical approaches how to deal with inter-dependencies.
| |
| Which mechanisms we can provide to deal with these inter-dependencies?
| |
| Other (future) points that appear in the discussion:
| |
| • Consider when the structure of the problem (dependencies among nodes) is
| |
| different from the communication network (what nodes can communicate
| |
| which each other and with what constraints)
| |
| Other points:
| |
| Depending in the criteria on choosing the K-neighbours the resultant net-
| |
| work would have intrinsicaly more or less modularity. All NK-graphs are
| |
| are K-regular graphs. Therefore the question is exists a subfamily of K-
| |
| regular graphs that has an inherently modular structure?
| |
| 3 Domain: the NK Model
| |
| As a framework of the analysis of these nearly-descomposable systems we will
| |
| take Stuart Kauffmans model of fitness landscapes (Kauffman & Levin 1987,
| |
| Kauffman 1993). This model is very similar to a famous and well-studied class
| |
| of models which arises in statistical physics called spin-glasses.In this model all
| |
| parts collaborate in order to get a global solution. In this model, N refers to
| |
| the number of elements of the system- number of agents, genes in a genotype,
| |
| amino acids in a protein. . . , etc. Each part makes a fitness contribution which
| |
| depends upon that part and upon K other parts among the N. Hence for each
| |
| element i in N, we define the following energy function:
| |
| E(K)
| |
| i (si ; si1 . . . sik ) (1)
| |
| Hence the energy function of an element is always defined over its own state
| |
| and the state of K neighbours more. These K other elements may be chosen
| |
| anyway. S is the number of element possible states. Typically S = 2. The value
| |
| that this function assigns to each of the 2K+1 possible input configurations is
| |
| assigned randomly from a uniform distribution between 0 and 1. The cardinality
| |
| of K ranges from a minimum value 0 to a maximum value N-1. K reflects how
| |
| richly cross-coupled the system is.
| |
| The energy or fitness of the entire lattice for any given configuration of
| |
| the elements of the system is defined as the average of the energy or fitness
| |
| contributions of the elements:
| |
| E(s) = 1
| |
| N
| |
| N
| |
| i=1
| |
| E(K)
| |
| i (si ; si1 ..sik ) (2)
| |
| This is the global function that the system tries to minimize or maximize
| |
| depending on the context.
| |
| References
| |
| [1] Aaron Clauset, Cristopher Moore, and M. E. J. Newman. Hierarchical struc-
| |
| ture and the prediction of missing links in networks. Nature, 453(7191):98–
| |
| 101.
| |
| [2] Aaron Clauset, M. E. J. Newman, and Cristopher Moore. Finding commu-
| |
| nity structure in very large networks. Physical Review E, 70:066111, 2004.
| |
