In contrast to traditional methods, based typically on
large scale agentbased simulations or on numerical solutions of
coupled nonlinear deterministic or stochastic differentialequations, our framework is based on inherently distributive and
approximative probabilistic approaches. Our methods to describe
uncertainty, information transfer and emergent properties in complexsystems are based on complex connected graphs. The techniques for
analysing such graphs derive from extensions of methods in statistical
physics to decompose high dimensional joint distributions into simpler,
computable quantities. The novelty of our method stems from the focus
on systems which exhibit this composite character: a combination of
localised and long range, sparse and dense, weak and strong
interactions between subcomponents in such graphs.
We are interested in exploiting complexity in
information systems which can be described by such graphs, but we are
using techniques from physics and modify them to be applicable to
inference in, and analysis of, complex systems.
This framework leads to new insights and fundamental
tools and techniques on generic systems which are applicable to many
important current real world problems, including CDMA coding methods,
adhoc sensor networks, distributive trafficlights management,
embedded intelligent sensors, and cortical functioning.
The investigators of this project are Prof David Saad and Prof David Lowe.
Funding

Funding source: EPSRC  EP/E049516/1

Funding amount: £ 322,747 (D. Lowe  CI).

Duration: 9/20079/2010
Project Background
The study of complexity has been identified as a key research area of significant future demand both by UK research councils and the EU and is supported through several dedicated programmes.
However, current methods to study complexity are based on large scale simulations, for instance of interacting agents, or on numerical solutions of coupled nonlinear deterministic or stochastic differential equations. Being of a large scale, highly nonlinear and inherently with multilevel interactions these methods are likely to be unsuccessful in providing generic theoretical insight as well as robust, principled and reliable solutions for specific instantiations of such systems. The main problems in these approaches are their sensitivity to model parameters and external observations, their sheer scale that prevents reliable numerical modelling and the difficulty in modelling and analysing systems with multilevel interactions.
The general approach that we propose for understanding such systems is based on probabilistic approximative and distributive methods that are local, scale well (linearly or at most quadratically) with the system size, accommodate variable and measurement uncertainties and readily provide confidence levels for the inferred variables. The macroscopic description in specific problems can be provided using methods of equilibrium statistical mechanics that exploit the large system size to provide typical and robust expectation values that characterise the system's behaviour. This gives generic theoretical and analytical description of the system and further understanding of its capabilities and limitations that are difficult to obtain numerically due to the computational effort required. For instance, the macroscopic framework will identify threshold values for the ratios between the strengths of dense and sparse interactions under which a composite system could provide optimal solutions, the types and quality of solutions obtained and the conditions under which a collaborative behaviour is likely to emerge.
The problem we focus on here is that of composite systems of huge numbers of elements with multilevel interactions. These are particularly difficult and challenging in complex systems since although principled approaches have been devised for very dense or for very sparse interaction systems, they fail for the composite multilevel systems we investigate. We aim to obtain insights into information inference and knowledge structures by taking inspiration from the physics of coupled, interacting manybody systems normally analysed by methods of equilibrium statistical physics.
The exemplar application domains we have in mind span novel embedded sensor systems, control of transportation flow systems such as networks of traffic lights, and information flow in nervous systems, all of which exhibit the phenomenon of local connections with longrange interactions. For instance, a distributive inference method for traffic light management would include information on the state of neighbouring traffic lights (strong interactions) as well as weak interactions with all traffic lights related to traffic coming into/outof town. Similarly, individual oscillators in a MEMS array of sensors will inevitably have local neighbourhood mechanical coupling combined with parasitic long range interactions leading to possible novel emergent behaviours and new selforganising sensor modalities.
A principled approach is required to determine the optimal state and to analyse such composite systems. We propose that insight into the complexity of such systems will derive from the interdisciplinary approach of extending concepts from physics across into the information/inference domain.
For instance, in the inference domain, probabilistic graphical models (Bayes belief networks) provide a powerful framework for modelling statistical dependencies between variables in systems that can be mapped onto sparse graphs (i.e., where the number of direct probabilistic dependencies per variable is much smaller than the number of system variables and interactions are characteristically strong). These methods play an essential role in providing principled approximate probabilistic inference in a broad range of applications from medical expert systems to telecommunication. (These methods, that have largely been developed independently in the computer science and information theory literature, can be derived from early results in statistical physics: belief propagation on graphs for instance, relates to stationary points of the Bethe approximation of the free energy dating back to 1935).
However, these methods and their variations are generally inappropriate for systems that are globally more densely connected (and where the interactions are characteristically weak) as the computational effort grows exponentially with the connectivity. Also, dense systems include a high number of loops in the corresponding graphical representation which cannot be generally tolerated by these methods (since one of the main approximations used is the weak dependence between variables that are not directly connected, which is clearly violated in the presence of loops).
On the other hand, different methods, based on meanfield approximations, have been suggested for obtaining solutions in the case of densely connected systems, where the number of connections is large and of the same order as the number of variables (while the
connection strength is relatively weak compared to the system size). However, these methods rely heavily on the fact that the system is very large and the interactions weak, through a sequence of approximations.
The same dichotomy exists in the methods used for analysing disordered physical systems, and systems that can be mapped onto disordered systems. The statistical physics methods used for analysing densely connected models, such as the SherringtonKirkpatrick model require different assumptions than those used in the study of sparsely connected systems. Although the models have originated in the statistical physics literature, very similar models have been used to study other complex systems such as neural networks, CDMA signal detection and errorcorrecting codes.
We have identified this particularly challenging area of systems' complexity of composite systems that include both naturally sparse, strong connections and weak, dense interactions. The proposal includes both the development of inference methods in composite systems, aimed at finding solutions for particular instances, and the analysis of generic systems with multilevel interactions where computational studies are intrinsically intractable.
Objectives
In this project we will:

Formalise relationships between the theory and techniques of inference in composite systems to specific realworld complexity aimed at developing generic tools.

Develop inference methods for composite systems that include both strong and weak interactions, which are randomly
connected in a sparse and dense manner, respectively.

Extend the new inference algorithms to problems that include more complex structures, such as local strongly connected regions with weak long range interactions.

Analyse composite models via methods of statistical physics to gain insight by studying the behaviour of such a composite system and to demonstrate the efficacy of such tools to the study of generic composite systems.
The success of the inference techniques developed will be assessed by the ability of the developed algorithms derived from principled theory to find successfully exact solutions for composite systems, compared with the performance of heuristic search algorithms. A successful analysis of generic composite physical systems, comprising interactions of various strengths and connectivities will enable us to gain insight into the behaviour of such generic complex systems, demonstrating the usefulness of the method for analysing complex systems. The insight obtained will include the identification of threshold for the system's parameters (e.g., ratios between the strengths of dense and sparse interactions) under which a composite system could provide optimal solutions both practically and theoretically, the solutions obtained in other regimes and parameter values, and under which conditions collaborative behaviour is likely to emerge.
Achievements
Publications
Journal papers

R. Alamino and D. Saad, Typical Behaviour ofRelays in Communication Channels, Phys. Rev. E 76, 061124
(2007)  AURA Preprint
 R.C. Alamino and D. Saad, Typical Kernel Size and Number of Sparse Random Matrices over Galois Fields: A Statistical

Physics Approach, Phys. Rev. E 77, 061123 (2008)  AUPreprint
 J. Raymond and D.Saad, Composite Systems of Dilute and Dense Couplings, J. Phys. A 41, 324014 (2008)
 T. Yano, T. Tanaka and D. Saad, A Mean Field Theory of Coded CDMA Systems, J. Phys. A 41, 324022 (2008)  AURA Preprint
 K.Y.M. Wong and D. Saad, Minimizing Unsatisfaction in Colourful Neighbourhoods, J. Phys. A 41, 324023 (2008)  AURA Preprint
 E. Mallard and D. Saad, Bayesian Inference by Message Passing in Composite Systems, Phys. Rev. E 78, 021107 (2008)  AURA Preprint
 J. Raymond and D. Saad, Composite CDMA  A Statistical Mechanics Analysis, Journal of Statistical Mechanics: Theory and Experiment 2009, P05015 (2009)  arXiv Preprint
 R.C. Alamino and D. Saad, Properties of Sparse Random Matrices over Finite Fields, Journal of Statistical Mechanics: Theory and Experiment 2009, P04017 (2009)  AURA Preprint

J. Raymond and D. Saad, Equilibrium Properties of Disordered Spin Models with Two Scale Interactions, Phys.
Rev. E 80, 031138 (2009)  AURA Preprint
 J. Reichardt, R. Alamino and D. Saad, The
interplay microscopic and mesoscopic structure in complex networks
(2010) submitted  arXiv Preprint
 M. F. Randrianandrasana, X. Wei, D. Lowe, APreliminary Study into Emergent Behaviours in a Lattice of InteractingNonlinear Resonators and Oscillators, Communications in Nonlinear Science and
Numerical Simulations, (2010)
 X. Wei, M. F. Randrianandrasana, M. Ward and D.
Lowe, Nonlinear Dynamics of a Periodically Driven Duffing Resonator Coupled toa Van der Pol Oscillator, Mathematical Problems in Engineering 2011, 248328 (2010)
Conferences proceedings
 D. Saad, J.P. Neirotti and E. Mallard, Inference by Message Passing in Dense and Composite Systems, Dagstuhl Seminar Proceedings on Similaritybased Clustering, Eds. M. Biehl, B. Hammer, M. Verleysen and T. Villmann, 8, 2007
 J. Raymond and D. Saad, Randomness and metastability in CDMA paradigms, 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, IEEE, 626630, 2008
 R.C. Alamino and D. Saad, Typical Performance of Generalised Vector Channels, 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, IEEE, 598602, 2008
 K.Y.M. Wong, D. Saad and C.H. Yeung, Network Optimisation  A Statistical Physics Perspective, 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, IEEE, 577582, 2008
 J. Raymond and D. Saad, Characteristic Behaviour of Composite Systems with Two Scale Interactions, Proceedings of the 5th European Conference on Complex Systems (electronic media) 2008
 X.
Wei, M. Ward, C. Anthony and D. Lowe, A preliminary study of a nonlinear micro
vibroimpact system, Proceeding of the 36th International Conference on
Micro & Nano Engineering, Italy, 19  22 2010
 M.
F. Randrianandrasana, X. Wei, D. Lowe, Collective Behaviour in a Square Latticeof Driven Duffing Resonators Coupled to van der Pol Oscillators, 785790, 2010
10th IEEE International Conference on Computer and Information Technology, 2010

X.
Wei, C. Anthony, D. Lowe and M. Ward, Design and Fabrication of a Nonlinear
Micro Impact Oscillator Procedia Chemistry 1,
855858, Proceedings of the Eurosensors XXIII conference, 2009
Presentations  oral
 R.C. Alamino and D. Saad, GF(q) Sparse Random Matrices: Some Properties
via Statistical Physics, NEXTSigmaPhi2008 International Conference in
Statistical Physics, 1418 July 2008, Kolymbari, Crete.
 J. Raymond and D. Saad, Composite CDMA  A
Statistical Mechanic Analysis, NEXTSigmaPhi2008 International Conference in
Statistical Physics, 1418 July 2008, Kolymbari, Crete.
 J. Raymond and D. Saad, Characteristic Behaviour
of Composite Systems with Two Scale Interactions, 5th European Conference on
Complex Systems, September 1419, 2008, Jerusalem.
 R.C. Alamino and D. Saad, Statistical Physics of
Sparse Random Matrices Over Finite Fields, The Science of Complexity, 29 March
 1 April 2009, Eilat, Israel. *
 R.C. Alamino and D. Saad, Statistical Physics of
Sparse Random Matrices Over Finite Fields, in a workshop of the Max Planck
Institute, ENRAGEing Perspectives  Random Geometry and Random Matrices: From
Quantum Gravity to Econophysics, May 1822, 2009, Dresden, Germany. *
 R.C. Alamino and D. Saad, Properties of Sparse
Random Matrices over Finite Fields, in Statistical Mechanics of Glassy and
Complex Systems, King's College London, 26 May 2009, London.
 D. Saad, Probabilistic Approaches to
Understanding Complex Systems, The NCAF (Natural Computing Application Forum)
Winter Meeting, 1920 January, 2010, Birmingham, UK. *
 D. Saad and J. Raymond, Inference and analysis of complex systems
with two scale interactions, Statistical Physics and Computer Science(Satellite
Meeting of STATPHYS24) 711 July 2010,
Beijing, China.*
*  By invitation
Presentation  poster
 J. Raymond and D. Saad, Randomness and
metastability in CDMA paradigms, PHYSCOMNET 2008, The 1st Workshop on
PhysicsInspired Paradigms in Wireless Communications and Networks, April 4th,
2008, Berlin, Germany
 R.C. Alamino and D. Saad, Typical Performance of
Generalised Vector Channels, PHYSCOMNET 2008, The 1st Workshop on PhysicsInspired
Paradigms in Wireless Communications and Networks, April 4th, 2008, Berlin,
Germany
 R.C. Alamino and D. Saad, LowDensity
ParityCheck Codes in Multiuser Channels: Statistical Physics Approach,
European Conference on Complex Systems' 09, University of Warwick, 2125
September, 2009
 D. Saad, D. Lowe, R.C. Alamino, J. Raymond and E. Mallard,
Complexity in Composite Systems, European Conference on Complex Systems' 09,
University of Warwick, 2125 September, 2009
 R. Alamino, J. Reichardt and D. Saad, Message
passing methods for community detection in complex networks, StatPhysHK,
Complexity, Computation, Information, (Hong Kong Satellite Meeting of
STATPHYS24), Hong Kong, 1316 July 2010