Table of Content
We thank the European Union project SOCIONICAL (FP7 ICT 231288) for financial support.
MatLab is the default research environment in many domains of science and industry. However, due to its focus on matrices, MatLab can't be efficiently used for network research.
The Complex Networks Toolbox for MatLab is a framework designed to allow efficient analysis of Networks within MatLab. Most of the computationally heavy algorithms are implemented in C++ and packaged into mex-files. The toolbox is easily expandable as its methos operate on the same data struct. The best part is that the analysis results are returned onto the familiar and powerful MatLab environment, whether they can be further explored or presented.
I do my best to support the toolbox users, so do e-mail me with any questions related to the package use or expansion.
I did my best to implement the most efficient (in terms of execution time and memory requirements) algorithms.The toolbox can manipulate and process graphs of over 10 million nodes and 100 million edges. Most algorithms cite the proper scientific source so their asymptotic efficiency can be easily estimated.
Static Network Analysis
The toolbox includes a large number of algorithms performing variety of network analysis tasks. Most of computationally heavy algorithms are implemented in C++ compiled into executable mex-files. Many of the algorithms receive “directionality” parameter that determines whether they should run on the actual graph (default), its inverse or the undirected version of the graph. Algorithms determining properties of individual nodes may receive a list of nodes of interest and save computational resources returning the result for a subset of nodes only.
The algorithms include (but are not limited) to extraction of node degrees, computation of mean degree of each node’s local network, different shortest path and distance measures (i.e. identification of nodes at or within particular distance or frequency of circles of different lengths), clustering coefficient, neighbourhood overlap, node and link embeddedness, variety of advanced centrality measures (i.e. betweenness) and ranking algorithms (i.e. HITS and PageRank), several graph partitioning methods (K-Shell and K-Core extraction, identification of weakly and strongly connected components, graph modularity), network motifs statistics.
Simulation of Dynamic Processes
Dynamic processes on networks, such as diffusion of innovation, spread of behaviour or contagious disease are in focus of researchers' interests in many domains. However, there are very few packages that facilitate high-level (yet efficient) simulation of dynamic processes on networks. The match with network generation, comprehensive network analysis capabilities, and layout makes the system very powerful.
The framework is designed to conceal the mechanics of the diffusion processes. The user just needs to define initialization (states of the nodes at the simulation launch, i.e. which behaviour the agents originally follow), a callback function defining individual agent’s switching behaviour (change of agent's state as a function of the states of her local environment) and a activation order (in which order the callback functions are called by the framework – usually randomly, without replacement, but the user can select from a list of options or implement her own).
The framework supports extremely complex diffusion models. For example, agents may consider individual traits, historty of their own states or the states of their neighbours, switch between arbitrary number of states or even maintain a vector of states (i.e. several interacting processes - such as adoption of health behavior and spread of disease - may run simultaniously)
Our implementation achieves two seemingly contradicting goals. One one hand, we wanted to relief the package user from the intricacies involved in such simulations. On the other hand, we wanted to allow simulation of contagion processes of arbitrary complexity. Relying on agent-based methodology based on a callback function specifying agent’s behaviour hides the engine's implementation details and encourages the user to think in an agent-based manner. She just needs to specify responses of a single agent, a very natural frame of mind for the definition of contagion processes. While this approach keeps the user’s task simple (simple models like SI or SIR require just 2-3 lines of code, please see the examples), it allows her to define very complex behaviour at the agent level. For instance, users may exercise arbitrarily complex decision processes and switch between multiple states depending on their personal properties, individual history and the current states of peers within their local network. All these parameters are passed to the user-defined callback function that returns the new state of the agent. Agent's adoption behavior may even depend on her physical location, so that the entire simulation can even embedded into a larger simulation involving movement and physical model.
We provide implementations for few standard models, including SI, SIR and SIS, and show their execution and results analysis in the Tutorials. These models can be implemented in just few lines of very simple code, without profound understanding of the framework intricacies.
Network Export and Layout
The framework can interface with several graph layout engines by exporting graphs in compatible formats or directly automating the engines. We export networks into native formats of yEd, At&t; graphviz and Pajek, however, automation of Gephi toolkit and At&t; GraphViz offer tighter integration as these tools can be operated directly from MatLab with much better control of the generated graphs. A sequence of generated images can merged into a movie examplifying, for instance contagion or diffusion process on network.
Integration of Gephi Toolkit facilitates programmatic (in MatLab) control of several layout algorithms, each with numerous attrributes, arbitrary graph coloring schemes (the individual node’s and edge’s size, color, shape or label can be set programmatically in MatLab), rendering and export options. We conceptualize graph layout as a sequence of “frames”, each frame potentially representing a different graph with different set of options and applied layout algorithms. The typical use would be execution of one of the force layout algorithms on the first frame only, so that the consequent graphs would have identical layout. The frames would, however, differ in color or size of the graph elements. Merging a sequence of graphs generated from a set of consequent frames into a movie could represent, for instance, diffusion process on a graph.
Similar approach can be taken with AT&T; GraphViz, software that can encode graph layout in text file with coordinates for each node and specification of curves representing edges. That file can be used to generate a sequence of frames differing in node/edge properties but preserving layout. These frames could be fed into yEd to generate a sequence of images.
We recommend using the Gephi Toolkit option since it's better integrated and supported.
Network I/O and generative models
The package implements a number of standard generative models and is well-suited for experiments with custom algorithms. It can import data in the most frequently used network file formats. Considering the growing number of students taking network courses, I've added a number of publically available empirical networks that can be used for education or testing.
Each of the implemented algorithms is thoroughly documented. The documentation includes description of all input and output parameters, definition of the function behavior for different inputs and a list of related algorithms, use examples and reference to publication when relevant.
The package operates on directional networks. Undirected graphs may be represented as directed graph with each link reciprocated by a link in the opposite direction. GraphMakeUndirectional method will automatically convert directed networks into undirected ones.
Arbitrary Node Properties
Each node may maintain a list of user-defined properties of any data type. These properteis can be easily accessed, updated and considered in various computations.
Network may mix various types of nodes, representing multi-layer networks. For example, affiliation network of researchers and their collaborations can be represented by a graph where some nodes are marked as researchers and others - as papers. This ability is based on the ability to maintain node properties as each node may belong to a specific layer of the network.
The basic data structure used in this version of the package fully supports weighted networks. However, only one weight may be assigned to each edge and most of the provided algorithms ignore weights at the current stage.
The toolbox builds upon MatLab which can run on many operating systems. However, the mex-files must be built on the particular platform. These algorithms are implemented in standard C++ code which may be easily compiled on any platform. Versions for Windows 32 and 64 and Linux/Mac OS and available. The credit for porting the most recent version of the library to Mac goes to Eben du Toit. Eben, many thanks for your help!
The Complex Networks Package for MatLab is a function-based library. As such, most of its algorithms are stand-alone and are independent of the rest (though, some methods may recursively call others). Addition of new algorithms is fairly straightforward. Even efficient implementation of computationally demanding algorithms within mex-files is easy ( I suggest using one of the existing mex-files as template).
In case you find the package helpful and publish your research, I'd approciate a reference:
|Feb 26, 2013||1.6||
MatLab 7, 32 & 64 bits
Feb 26, 2013
MatLab 7 64 bit
Feb 26, 2013
Check out the news page for recent functionality changes and bug fixes.
|April 4, 2012||1.4||
Windows, MatLab 7, 32 bits
April 4, 2012
Win 32, MatLab 7, x64
April 4, 2012
Win 32, MatLab 7, 32 & 64 bits in one archive
|April 4, 2012||1.4||
Windows Sources, MS Visual Studio 2010
Mac / Linux(ported by Guy Kelman)
|June 1, 2012||1.4||Mac / Linux, m-files||0.7Mb||ComplexNetworkPackageLinuxMFiles.v14.zip|
|June 1, 2012||1.4||Mac / Linux, i386 binaries||0.7Mb||ComplexNetworkPackageLinuxV14.i386.tar.gz|
|June 1, 2012||1.4||Mac / Linux, x64 binaries||0.7Mb||ComplexNetworkPackageLinuxV14.x64.tar.gz|
*Note that the binary packages contain only binaries that, once built, should complement the m-files in the first package (ComplexNetworkPackageLinuxMFiles.v14.zip). See the Mac/Linux Install section below for more details.
The Windows version of the Complex Network Package requires Mathwork's MatLab version 7 or higher. Both 32 and 64 bit versions are supported under MS Windows.
To install the package
- Download and unpack the appropriate version
- Add 'Graph' , 'FlexIO', 'DynamicProcess' and 'FastSet' folders to your MatLab path (File -> Set Path menu)
- Don't forget to save the MatLab path.
- Few of the Graph package routines (the ones located in the DynamicProcess folder) make use of the FastSet methods (present in the zip file you've downloaded) that use some additional Microsoft's libraries. You will only need them if you run dynamic processes simulations as described in Tutorial 2. Check you Windows/System32 folder for MSVCR110.DLL and MSVCP110.DLL to see whether you already have these libraries installed. If not, you'll need to install the appropriate package from Microsoft's web site.
- You are done
The Mac/Linux port of the toolbox was generously contributed by Guy Kelman. To install the package
- Unpack the m-files in the first raw of the Mac/Linux table
- Build the x32 or the 64-bit version depending on the version of MatLab you have and add the obtained binaries along with the corresponding m-files to the main Graph folder.
- Add 'Graph' and 'FlexIO' folders to your MatLab path (File -> Set Path menu)
- Don't forget to save the MatLab path.
- You are done
Check out this brief tutorial that shows few of the Complex Networks Package for MatLab typical uses.
You are most welcome to write me directly with both technical and theoretical questions.