ModularityNDS - Revision history

Meritxell at 15:22, 17 June 2008

2008-06-17T15:22:53Z

← Older revision		Revision as of 15:22, 17 June 2008
Line 7:		Line 7:
	* Orion Penner		* Orion Penner
	* Meritxell Vinyals		* Meritxell Vinyals

			Join us if you are interested in the proposal below!!!

	== Project Proposal ==		== Project Proposal ==

	[[Media:project_proposal.pdf \| project_proposal.pdf]]		[[Media:project_proposal.pdf \| project_proposal.pdf]]

Meritxell at 15:22, 17 June 2008

2008-06-17T15:22:29Z

← Older revision		Revision as of 15:22, 17 June 2008
Line 10:		Line 10:
	== Project Proposal ==		== Project Proposal ==

	[[Media:project_proposal.pdf \| ~~hola~~]]		[[Media:project_proposal.pdf \| project_proposal.pdf]]

Meritxell at 15:22, 17 June 2008

2008-06-17T15:22:07Z

← Older revision		Revision as of 15:22, 17 June 2008
Line 3:		Line 3:
	== Project Members ==		== Project Members ==

			* Adam Campbell
			* Laura Feeney
			* Orion Penner
			* Meritxell Vinyals

	== Project Proposal ==		== Project Proposal ==

	[[Media:project_proposal.pdf]]		[[Media:project_proposal.pdf \| hola]]

Meritxell at 15:20, 17 June 2008

2008-06-17T15:20:10Z

← Older revision		Revision as of 15:20, 17 June 2008
Line 6:		Line 6:
	== Project Proposal ==		== Project Proposal ==

	[[~~Image~~:project_proposal.pdf]]		[[Media:project_proposal.pdf]]

Meritxell at 15:19, 17 June 2008

2008-06-17T15:19:48Z

← Older revision		Revision as of 15:19, 17 June 2008
Line 6:		Line 6:
	== Project Proposal ==		== Project Proposal ==

	~~Simon Herbert~~ [~~5] discusses a broad ranging set of systems (business, biological~~		[[Image: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 aﬀected.~~
	~~A strong inter-dependency among modules is deﬁned as one the stability of a~~
	~~given conﬁguration of one or both modules is sensitive to the attractor module~~
	~~and this conﬁguration which is most stable may also diﬀer. In other words, we~~
	~~have to check if modules attractors are aﬀected or unaﬀected 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 ﬁts on the complexity and on the underlying network; 2) in case of a hierar-~~
	~~chy, deﬁne the organization or how to deal with the inter-module dependencies;~~
	~~and 3) ﬁnding a strategy of search within the given submodule.~~
	~~Our approach:~~
	~~• Use as a framework of analysis for the nearly-descomposable systems the~~
	~~Stuart Kauﬀmans model of ﬁtness 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~~
	~~diﬀerent 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 Kauﬀmans model of ﬁtness landscapes (Kauﬀman & Levin 1987,~~
	~~Kauﬀman 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 ﬁtness contribution which~~
	~~depends upon that part and upon K other parts among the N. Hence for each~~
	~~element i in N, we deﬁne the following energy function~~:
	~~E(K)~~
	~~i (si ; si1 . . . sik ) (1)~~
	~~Hence the energy function of an element is always deﬁned 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 conﬁgurations 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 reﬂects how~~
	~~richly cross-coupled the system is.~~
	~~The energy or ﬁtness of the entire lattice for any given conﬁguration of~~
	~~the elements of the system is deﬁned as the average of the energy or ﬁtness~~
	~~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.~~

Meritxell at 15:17, 17 June 2008

2008-06-17T15:17:26Z

New page

= Hierarchical modularity of nearly-descomposable systems =

== Project Members ==

== 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 aﬀected.
A strong inter-dependency among modules is deﬁned as one the stability of a
given conﬁguration of one or both modules is sensitive to the attractor module
and this conﬁguration which is most stable may also diﬀer. In other words, we
have to check if modules attractors are aﬀected or unaﬀected 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 ﬁts on the complexity and on the underlying network; 2) in case of a hierar-
chy, deﬁne the organization or how to deal with the inter-module dependencies;
and 3) ﬁnding a strategy of search within the given submodule.
Our approach:
• Use as a framework of analysis for the nearly-descomposable systems the
Stuart Kauﬀmans model of ﬁtness 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
diﬀerent 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 Kauﬀmans model of ﬁtness landscapes (Kauﬀman & Levin 1987,
Kauﬀman 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 ﬁtness contribution which
depends upon that part and upon K other parts among the N. Hence for each
element i in N, we deﬁne the following energy function:
E(K)
i (si ; si1 . . . sik ) (1)
Hence the energy function of an element is always deﬁned 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 conﬁgurations 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 reﬂects how
richly cross-coupled the system is.
The energy or ﬁtness of the entire lattice for any given conﬁguration of
the elements of the system is deﬁned as the average of the energy or ﬁtness
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.