Compression of Weighted Graphs

We propose to compress weighted graphs (networks), motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplication, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized. In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of 'generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with dierent balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.

Essays on labour demand and wage formation

The first essay in this thesis is on gender wage differentials among manufacturing sector white-collar workers. The wage differential is decomposed into firm, job (within-firm) and individ-ual-level components. Job-level gender segregation explains over half of the gap, while firm-level segregation is not important. After controlling for firm, job and individual characteristics, the remaining unexplained wage cap to the advantage of men is six per cent of men s mean wage. In the second essay, I study how the business cycle and gender affect the distribution of the earnings losses of displaced workers. The negative effect of displacement is large, persistent and strongest in the lowest earnings deciles. The effect is larger in a recession than in a recov-ery period, and in all periods women s earnings drop more than men s earnings. The third essay shows that the transition from steady employment to disability pension de-pends on the stringency of medical screening and the degree of experience-rating of pension costs applied to the employer. The fact that firms have to bear part of the cost of employees disability pension costs lowers both the incidence of long sick leave periods and the probabil-ity that sick leave ends in a disability pension. The fourth and fifth essays are studies on the employment, wage and profit effects of a re-gional payroll tax cut experiment conducted in northern and eastern Finland. The results show no statistically significant effect on any of the response variables.