ModularityNDS

Hierarchical modularity of nearly-descomposable systems

Project Proposal

Simon Herbert [5] discusses a broad ranging set of systems (business, biological . . . ) 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.