# Seminar on Complex Networks

Kristina Ban, Faculty of Social Sciences, Faculty of Information Studies, Novo mesto, Slovenia

A short review of network aligners

Wednesday, 6.5.2015, at 14:00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

Among the most challenging problems in network analysis is the comparison of two networks, i.e., the quantification of their topological difference. The challenge comes from this being an NP-hard problem, due to the underlying subgraph isomorphism. Thus, we rely on heuristics through different comparative methods, such as network integration, network querying and the most common one, network alignment. In this talk we will present a short survey of network alignment.

dr. Luka Kronegger, Faculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia

Structures of collaboration in Slovenian science system

Tuesday, 21.4.2015, at 16.00 - 18:00, classroom nr. 5 (1 st floor), Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

Co­authorship as form of scientific collaboration presents the major interaction mechanism between actors at the micro­level of individual scientists. Wide range of mechanisms fostering collaboration produce different local patterns within general network which can be described from the perspective of research groups, research topics, intensiveness of collaboration or comparison of entire research disciplines. In our research we observed and compared collaborative structures in complete longitudinal co­authorship networks for four research disciplines. Dataset was split into 4 five­year intervals and clustered with blockmodeling technique. The main question of the research was to what extent the obtained multi­core periphery structure is determined by organizational structure of the institutions, special topics in the scientific field and other factors that foster scientific collaboration as research projects.

Andrej Kastrin, Faculty of Information Studies, Novo mesto, Slovenia

Uvrščanje in diskretizacija mnogorazsežnih podatkovnih tabel
Monday, 8.12.2014, at 13.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

Tehnologija DNA mikromrež je danes dostopna v vsakem bolje opremljenem biomedicinskem laboratoriju. Kljub dovršenosti postopkov predstavlja statistična analiza mikromrežnih DNA podatkovij za statistika še zmeraj velik izziv. Mikromrežno podatkovje opišemo z matriko razsežnosti n × p, kjer se vrstice matrike nanašajo na posamezne primere, stolpci pa na proučevane gene. Velja, da je n << p. Na osnovi analize geometrijskih lastnosti mnogorazsežnih podatkovnih objektov lahko pokažemo, da je v tem primeru podatkovni prostor zelo redek. Fenomenu praznega prostora se poskušamo izogniti z uporabo metod za krčenje podatkovne strukture. Empirična evidenca razkriva, da na področju statistične analize mikromrežnih DNA podatkovij sistematična raziskava, ki bi proučevala vpliv metod za krčenje podatkovnih struktur, še ni bila opravljena. Prav tako ostaja odprto vprašanje smiselnosti diskretizacije mikromrežnih podatkov. V seminarju obravnavamo tri problemske naloge. V prvem sklopu eksperimentov smo proučili kakovost različnih klasifikatorjev v nalogi uvrščanja primerov v dva vnaprej podana razreda. Uporabili smo nekatere najpogosteje uporabljene medote, kot so nevronske mreže, metoda najbližjih sosedov, klasifikacijska drevesa s slučajnimi gozdovi, metoda podpornih vektorjev, logistična regresija s kaznijo ter tri izpeljanke linearne diskriminantne analize (Fisherjeva, klasična in diagonalna). V drugi problemski nalogi smo analizirali vpliv metod za kršenje št. razsežnosti na uvrščanje. Podrobno smo proučili vpliv analize glavnih komponent in metode delnih najmanjših kvadratov na kakovost uvrščanja. V tretjem sklopu smo se ukvarjali s proučevanjem vpliva diskretizacije neodvisnih spremenljivk na uvrščanje. V analizo smo vključili nekatere najpogosteje uporabljene algoritme diskretizacije, kot so metode enake širine intervalov, enake zastopanosti intervalov, 1R, MDLP in ChiMerge. Eksperimente smo izvedli nad 37 realnimi DNA mikromrežnimi podatkovji. Pri uvrščanju realnih mikromrežnih podatkovij se najbolj odreže logistična regresija s kaznijo, najslabše pa nevronske mreže. Med metodama krčenja podatkovne matrike glede na kakovost uvrščanja ni statistično značilnih razlik. Med metodami diskretizacije se glede na uvrščanje najbolje odrežeta metodi MDLP in ChiMerge. Seminar zaključimo s pregledom možnosti za nadaljnje delo.

Jelena Govorčin, Faculty of Information Studies, Novo mesto, Slovenia
The degree-weighted betweenness centrality and its extremal values
Wednesday, 14. 5. 2014, at 14.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

The vertex (resp. edge) betweenness centrality measures the degree to which a vertex (resp. edge) is participating in the communication between pairs of other vertices. At this seminar we introduce degree-weighted betweenness centrality. The motivation for new invariant is found in the idea that monitoring of an edge is not done by both end-vertices simultaneously all the time and that work on each vertex can be allocated based only on the local information. The goal of this study was to determine the extremal values of the introduced measure, as well as the graph structures where the extremal values are attained. Several real world networks were used for evaluation of the new invariant.

Uroš Mesojedec, T-media and Faculty of Information Studies, Novo mesto, Slovenia
Programska oprema v oblaku
Wednesday, 2. 4. 2014, at 13.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

S širitvijo pomembnosti računalniškega oblaka (computer cloud) se pojavljajo novi izzivi pri pripravi in razvoju programske opreme. Hkrati je oblak najsodobnejša pojavna oblika razpršenih računalniških omrežij. Kakšni so lahko pristopi pri prenosu obstoječe programske opreme v oblak? Kako ga lahko ta programska oprema najboljše izkoristi? Katere so možne aplikacije programske storitve v oblaku, tudi pri analizi samih omrežij? Odgovore na ta in podobna vprašanja bomo predstavili na sredinem seminarju.

Vesna Andova, Faculty of Information Studies, Novo mesto, Slovenia, and, St Cyril and Methodius University, Skopje, Macedonia
Bounds on saturation number of fullerene graphs
Wednesday, 26. 2. 2014, at 15.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

The saturation number of a graph G is the cardinality of any smallest maximal matching of G, and it is denoted by s(G). Fullerene graphs are cubic planar graphs with exactly twelve 5-faces; all the other faces are hexagons. Here we show that the saturation number for fullerenes on n vertices is essentially n/3.

František Kardoš, Université de Bordeaux, France
One of Barnette's conjectures confirmed: (not only) fullerene graphs are hamiltonian
Wednesday, 26. 2. 2014, at 14.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

Fullerene graphs, i.e., 3-connected planar cubic graphs with pentagonal and hexagonal faces, are conjectured to be hamiltonian. This is a special case of a conjecture of Barnette, dating back to the 60s, stating that 3-connected planar cubic graphs with faces of size at most 6 are hamiltonian. We present a computer-assisted proof of the conjecture.

mag. Katarína Hrináková, Slovak University of Technology, Bratislava, Slovakia
Self-dual, self-Petrie-dual, and Möbius regular maps on linear fractional groups
Wednesday, 15. 1. 2014, at 13.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

Maps are cellular embeddings of graphs on compact surfaces. Regular maps are maps with highest possible level of symmetry. A map is regular if its automorphism group acts regularly on the set of its flags. Enumeration and classification of regular maps is usually approached in three different ways - by supporting surfaces, by underlying graphs, and by automorphism groups. In this talk we focus on regular maps whose automorphism group is isomorphic to ${\rm PSL}(2,q)$ and ${\rm PGL}(2,q)$ and will characterize those maps which are self-dual, self-Petrie-dual, or Möbius.

dr. Borut Lužar, Faculty of Information Studies, Novo mesto, Slovenia
Community detection in networks
Wednesday, 15. 1. 2014, at 12.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

In networks from a wide range of domains one can recognize community structures. There is no unique definition of a community; its most common accepted description is to be a set of vertices C with a high number of edges with both endvertices from C, whereas there are only few edges with exactly one endvertex in C. Determination of a community structure of a network is important for various reasons; it can reveal functional organization of networks, it is useful for the visualization etc. A number of algorithms have been developed to achieve this task. It the talk we will shortly describe the problem and sketch a couple of algorithms for community detection.

dr. Aleš Lapajne, Institute of Microbial Sciences and Technologies, Domžale, Slovenia
What is the critical step that follows the genomic and metagenomic analysis of microorganisms?
Wednesday, 8. 1. 2014, at 13.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

The lecturer will talk about the following topics:
1. The problems that scientists are deling with in the field of microbiology and presentation of analytical analyses, which provide insight into microbial world.
2. Data structure for 1 degree of metagenomic analysis.
3. Structure of genomic data analysis structure of databases.
4. Data structure in the analyses of the secondary structures of DNA/RNA molecules.

dr. Borut Lužar, Faculty of Information Studies, Novo mesto, Slovenia
Interdisciplinarity of Slovenian research
Wednesday, 11. 12. 2013, at 13.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

The growth of modern science is fastest along the borderlines between the traditional disciplines. Interdisciplinarity usually benefits all fields involved in a given research despite their diversity. In this short report, we analyze the current state of interdisciplinary science in Slovenia. By detecting the communities in co-authorship networks we investigate the raise of interdisciplinary research groups from 1960 to 2000. Our preliminary findings indicate that although interdisciplinarity is clearly gaining ground in Slovenian research landscape, there are still many barriers to overcome.

Milovan Suvakov, Institute of Physics, Belgrade, Serbia
The Newtonian three-body problem: 13 new periodic solutions and topological classification
Tuesday, 10. 9. 2013, at 13.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

The three-body problem dates back to the 1680s. Isaac Newton had already shown that his law of gravity could always predict the orbit of two bodies held together by gravity, such as a star and a planet, with complete accuracy. The periodic two-body orbit is always an ellipse (sometimes turning into a circle). For two centuries, scientists tried different tacks to find similar solution for three-body problem, until the German mathematician Heinrich Bruns pointed out that the search for a general solution for the three-body problem was futile, and that only specific solutions that work only under particular conditions, were possible. Only three families of such collisionless periodic orbits were known until recently: 1) the Lagrange-Euler (1772); 2) the Broucke-Henon (1975); and 3) Cris Moore's (1993) periodic orbit of three bodies moving on a "figure-8" trajectory. We report the discovery of 13 new families of periodic orbits, bringing the new total to 16. We discuss the numerical methods used to find them and distinguish them from others, as well as the next steps in this line of research (e.g. to see how many of the new solutions are stable and will stay on track if perturbed a little: If some of the solutions are stable, then they might even be glimpsed in real life.).

Martin Knor, Faculty of Civil Engineering, Slovak University of Technology, Bratislava, Slovakia
Deterministic self-similar models of complex networks
Wednesday, 26. 6. 2013, at 13.00 seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

Using very symmetric graphs we generalize several deterministic self-similar models of complex networks and we calculate the main network parameters of our generalization. More specifically, we calculate the order, size and the degree distribution, and we give an upper bound for the diameter and a lower bound for the clustering coefficient. These results yield conditions under which the network is a self-similar and scale-free small world network. As a consequence, we can construct complex networks having prescribed properties. We demonstrate this fact on the clustering coefficient.

Roman Sotak, Pavol Jozef Šafárik University, Košice, Slovakia
Strong edge coloring
Wednesday, 19. 6. 2013, at 13.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

A strong edge coloring of a graph G is a proper edge coloring in which each color class is an induced matching of G; that is, there is no bichromatic path of length three in G. The minimum number of colors of a strong edge coloring of G is called the strong chromatic index of G and denoted by X'(G). In 1993 Brualdi and Quinn conjectured that every bipartite graph with bipartition X and Y without any cycle of length four such that the maximum degree of any vertex in X is two and the maximum degree of any vertex in Y is D can be strongly colored with D + 2 colors. We prove that this conjecture is true for such graphs with D = 3. We also confirm one of the conjectures for subcubic bipartite graphs introduced by Faudree et al. in 1990.

Borut Lužar, Faculty of Mathematics and Physics, Ljubljana, Slovenia
Edge colorings and partitions
Wednesday, 29. 5. 2013, at 13.00, seminar room of the Faculty on information studies (Ulica talcev 3, Novo mesto, Slovenia)

Several results on various types of edge colorings will be presented. In particular, proper edge colorings with additional assumptions and edge partitions will be considered. Additionally, two types of improper edge colorings with conditions regarding the face incidence of embedded graphs will also be mentioned.