Invited Session Thu.2.H 3002

Thursday, 13:15 - 14:45 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Network clustering


Chair: Sergiy Butenko



Thursday, 13:15 - 13:40 h, Room: H 3002, Talk 1

Michael Ovelgönne
Ensemble learning for combinatorial optimization: Modularity maximization and beyond

Coauthor: Andreas Geyer-Schulz


Modularity maximization is the NP-hard problem of identifying a graph partition with a maximal value of the quality measure modularity. Modularity maximization is a well-studied problem in the area of community detection in networks and attracted much attention in computer science as well as physics. A vast number of algorithms have been proposed for this problem. The core groups graph clustering (CGGC) scheme is an ensemble learning clustering method with very high optimization quality. This method combines the local solutions of several base algorithms to form a good start solution (core groups) for the a final algorithm. Especially iteratively finding good restart points showed to result in very good optimization quality. We will draw an analogy between the discrete problem of modularity maximization with nonlinear optimization in finite dimensions. We will show that core groups are the discrete counter-parts of saddle-points and that they constitute good restart points for greedy algorithms. While we developed the CGGC scheme for graph clustering, we believe this optimization scheme can be applied to many other combinatorial optimization problems as well.



Thursday, 13:45 - 14:10 h, Room: H 3002, Talk 2

Andrea Schumm
Experiments on density-constrained graph clustering

Coauthors: Robert Görke, Dorothea Wagner


Clustering a graph means identifying internally dense subgraphs which are only sparsely interconnected.
Formalizations of this notion lead to measures that quantify the quality of a clustering and to algorithms that actually find clusterings.
Since, most generally, corresponding optimization problems are hard, heuristic clustering algorithms are used in practice, or other approaches which are not based on an objective function.
In this work we conduct a comprehensive experimental evaluation of the qualitative behavior of greedy bottom-up heuristics driven by cut-based objectives and constrained by intracluster density, using both real-world data and artificial instances.
Our study documents that a greedy strategy based on local-movement is superior to one based on merging.
We further reveal that the former approach generally outperforms alternative setups and reference algorithms from the literature in terms of its own objective, while a modularity-based algorithm competes surprisingly well.
Finally, we exhibit which combinations of cut-based inter- and intracluster measures are suitable for identifying a hidden reference clustering in synthetic random graphs.



Thursday, 14:15 - 14:40 h, Room: H 3002, Talk 3

Cong Sun
Low complexity interference alignment algorithms for desired signal power maximization problem of MIMO channels


The Interference alignment technique is newly brought into wireless
communication to improve the communication capacity. For a K-user MIMO
interference channel,
we propose a low complexity interference alignment algorithm to solve
the desired signal power maximization problem, which is a nonconvex
complex matrix optimization problem.
First we use a courant penalty function technique to combine the
objective function as desired signal power with the interference
constraint, leaving only the orthogonal constraints. By introducing the
Householder transformation, the matrix problem turns into vector
optimization problem. Applying the alternating direction method and the
two-dimensional subspace method, the computational complexity of the
algorithm is greatly reduced. To overcome the disadvantage of this
algorithm to converge slowly around the local optimal solution, it is
combined with a higher complexity algorithm which helps to perfectly
eliminate interference and satisfy the original constraints. Simulations
show that compared to the existed algorithms, the hybrid algorithm needs
less computing time and achieves good performance.


  . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.