Section 2

Why Exponential Quality function cannot recognize bad communities in complex networks as modularity

Dušan Džamić, Nenad Mladenovic, Miroslav Marić

One of the most important properties of graphs which represent real complex systems is community structure, i. e. organization vertices in cohesive groups with high concentration of edges within individual groups and low concentration of edges between vertices in different groups. Such groups of vertices are called clusters (modules, communities) and very often have common features and roles in a complex system. The most common approach for clustering on complex networks is to define so called quality function, a function that measures the quality of partitioning of a network, and to construct methods for finding optimal partition with respect to defined function. Various quality functions, have been proposed such as minimum-sum-of-squares, edge-ratio, modularity and recent Exponential Quality (E-Quality) function. We considered different classes of artificial network from literature and analyzed whether the maximization of E-Quality function tends to merge or split clusters in optimal partition even those that are unambiguously defined. Moreover we evaluate the validity and reliability of the E-Quality function on real-world networks using the Variable Neighborhood Search (VNS) based heuristic. Results showed that E-Quality function detects the expected and reasonable clusters in all classes of instances as opposed to the modularity function.

Hydro-chain scheduling with alternating VND

Marko Mladenovic

The hydro-chain or hydro unit commitment problem is at the center of renewable power production. It determines which turbines will be activated and at what time in order to secure enough electrical power in the grid for a given day. From a combinatorial optimization standpoint, its mixed-integer programming model is very complex and is solved in advance in practice. If the power grid experiences unexpected events these solutions become obsolete. This is why the research community invested a significant effort to produce efficient approximations that could provide high-quality solutions in much less time. The literature offers a number of (meta-) heuristics for it. In this presentation, we describe how a VNS-based heuristic can be implemented. Initial results on real data are reported.