Notes
In most networks some edges or vertices are more central than others. To quantify importance of nodes in networks, centrality indices were introduced. For a given structural index, Freeman centralization is a measure of how central a vertex is regarding to how central all the other vertices are with respect to the given index. In the thesis we study several such structural indices like degree, eccentricity, closeness, betweenness centrality, the Wiener index and transmission. We confirm a conjecture by Everett, Sinclair, and Dankelmann regarding the problem of maximizing closeness centralization in two-mode data, where the number of data of each type is fixed. Intuitively, our result states that among all networks obtainable via two-mode data, the largest closeness is achieved by simply locally maximizing the closeness of a node. Mathematically, our study concerns bipartite networks with fixed size bipartitions, and we show that the extremal configuration is a rooted tree of depth ?$2$?, where neighbors of the root have an equal or almost equal number of children. We determine the maximum value of eccentricity centralization and (some) maximizing networks for the families of bipartite networks with given partition sizes, tree networks with fixed maximum degree and fixed number of vertices, and networks with fixed number of nodes or edges. As a by-product, we introduce and study a new way of enumerating the nodes of a tree. We also study the centralization of transmission, in particular, we determine the graphs on n vertices which attain the maximum or minimum value. Roughly, the maximizing graphs are comprised of a path which has one end glued to a clique of similar order. The minimizing family of extremal graphs consists of three paths of almost the same length, glued together in one endvertex. Group centrality indices, introduced in 1999 by Borgatti and Everett, measure the importance of sets of nodes in networks. We study the notion of group centralization with respect to eccentricity, degree and betweenness centrality measures. For groups of size ?$2$?, we determine the maximum achieved value of group eccentricity and group betweenness centralization and describe the corresponding extremal graphs. For group degree centralization we do the same with arbitrary size of group. For a given integer ?$k$?, by reduction to maximum domination problem, we observe that determining the maximum group degree centralization some ?$k$?-subset of ?$V(G)$? is ?${\mathcal NP}$?-hard. We describe polynomial algorithm with the best possible approximation ratio that calculates all centralizations for ?$1 \le k \le n$? and altogether runs in ?${\mathcal O}(n^2)$? time. The constructed algorithm is tested on six real-world networks. In results we observe a property of unimodality of group degree centralization for parameter ?$k$?, which may be a new property for studying networks. The well studied Wiener index ?$W(G)$? of a graph ?$G$? is equal to the sum of distances between all pairs of vertices of ?$G$?. Denote by ?$W{\mathcal G}_n$? the set of all values of the Wiener index over all connected graphs on $n$ vertices and let the largest interval which is fully contained in ?$W{\mathcal G}_n$? be denoted by ?$W^{\rm int}_n$?. In the thesis, we show that ?$W^{\rm int}_n$? is well-defined, it starts at ?${n \choose 2}$?, and that both ?$W^{\rm int}_n$? and ?$W{\mathcal G}_n$? are of cardinality ?${1 \over 6}n^3 + {\mathcal O}(n^2)$? (in other words, most of integers between the smallest value ?${n \choose 2}$? and the largest value ?${n+1 \choose 3}$? are contained in ?$W^{\rm int}_n$? and consequently in ?$W{\mathcal G}_n$?.