Blockmodeling multilevel and temporal networks

Code:

J7-8279

Period:

1.5.2017 - 30.4.2020

Range on year:

0.60 FTE | 2017

Project leader at FDV:

prof.dr. Aleš Žiberna

Research activity:

Interdisciplinary research

The phases of the project and their realization:

The project will be conducted by researchers who mainly already work together a lot. These are primarily established researchers from different areas of network analysis, which is appropriate in the light of the project objectives. The researchers come from two organisations, the Faculty of Social Sciences at University of Ljubljana (FSS) and the Institute of Mathematics, Physics and Mechanics (IMPM). The work will be divided into 11 work packages (WP). Below, we again present an approximate division of the WPs among the two organisations and list the core tasks (some less tangible tasks are omitted) with estimated times of completion (for individual tasks within WPs the estimated time of completion is only indicated if it does not match the end of the time slot for the WP): 1. WP1 – Common preparation phase. Duration – 12 months (months 1 – 12). Participants: Everybody a. Final literature review b. Assessment of the appropriateness of a common approach to blockmodeling linked networks or the need for different approaches for blockmodeling different kinds of linked networks c. Preparation of at least two (one multilevel and one temporal) empirical linked networks for testing (month 4) d. Preparation of a collection of empirical linked networks which can be used for testing and developing the new methods e. Construction of an algorithm or recommendations for generating random linked networks 2. WP2 – Studying mechanisms that lead towards a selected block structure. Duration – 30 months (months 1 – 30). Participants: Mainly the FSS group a. Studying mechanisms that lead towards a selected block structure b. Studying mechanisms that can cause one block structure to change into another block structure c. To use the findings for generating networks with a changing block structure in time 3. WP3 – Preparation phase for the development of optimisation methods. Duration – 8 months (months 5 – 12). Participants: Mainly the IMPF group, mainly for item f also other members a. Literature review for the field of optimisation methods for clustering and in particular blockmodeling b. Assessment of the suitability of different optimisation methods for linked networks c. At least one suggestion for an optimisation method to be used in generalised blockmodeling of linked networks (month 9) d. Assessment of the need for special methods for the optimisation of linked networks and, if needed, the design of such methods e. Assessment of the suitability of multicriteria optimisation f. Recommendations regarding the weighting of different parts of the networks in linked networks 4. WP4 – Development of optimisation methods for generalised blockmodeling of linked networks. Duration – 18 months (months 10 – 27). Participants: Mainly the IMPF group a. Selection and, if needed, adaptation of existing and/or design of new optimisation algorithms for generalised blockmodeling of linked networks (month 18) Public call for co-financing of research projects in 2017 b. Test implementation of selected algorithms (month 24) c. Testing selected algorithms on empirical or, if needed, randomly generated networks; a comparison with existing methods in terms of both quality and time complexity 5. WP5 – Final implementation and testing of generalised blockmodeling of linked networks with new optimisation methods. Duration – 9 months (months 24 – 32). Participants: Mainly the IMPF group a. Improvement of the methods created in WP4 (month 28) b. Implementation of the developed methods with special emphasis on time complexity and incorporation into a package for the statistical package R c. Testing on empirical and, if needed, randomly generated networks 6. WP6 – Preparation phase for the development of approaches for stochastic blockmodeling and blockmodeling based on the two-mode k-means method. Duration – 8 months (months 5 – 12). Participants: Mainly the FSS group a. Literature review of stochastic blockmodeling and blockmodeling based on k-means b. Preliminary selection of one or more approaches upon which the adaptations on linked networks will be based (month 9 for at least one approach) c. Assessment of the possibility of using or adapting approaches for special kinds of linked networks (mainly temporal) on/for other kinds of linked networks 7. WP7 – Development of stochastic blockmodeling approaches or approaches based on k-means for linked networks Duration – 18 months (months 10 – 27). Participants: Mainly the FSS group a. Development of the adaptation of suitable approaches and design of algorithms (month 18) b. Test implementation of selected algorithms (month 24) c. Testing selected algorithms on empirical and, if needed, randomly generated networks; a comparison with alternative approaches (at least Žiberna 2014) in terms of both quality and time complexity 8. WP8 – Final implementation and testing of stochastic blockmodeling approaches and/or approaches based on k-means. Duration – 9 months (months 24 – 32). Participants: Mainly the FSS group a. Improvement of the methods created in WP7 (month 28) b. Implementation of the developed methods with emphasis on time complexity and incorporation into the package for statistical package R c. Testing on empirical and, if needed, randomly generated networks 9. WP9 – Merging the results of all WPs, common comparisons of methods and presentation of the results. Duration – 12 months (months 25 – 36). Participants: Everybody a. Merging the results of all WPs, especially from both project branches b. Common comparisons of methods c. Dissemination of the results, also in thematic (special) section(s) within an international conference on network analysis 10. WP10 – Application of the developed methods to networks from the field of collaboration in science. Duration – 18 months (months 19 – 36). Participants: Mainly the FSS group a. Application to networks at several time points b. Application to multilevel networks c. If data are available, also application to multilevel networks at several time points d. Findings based on all these analyses 11. DP11 – General project management. Duration – 36 months (months 1 – 36). Participants: Mainly the project leader and leader of the IMPM group with technical staff a. Reports as required b. The final report

Abstract:

BACKGROUND: Blockmodeling is a method for partitioning the units of a network and determining the ties among the (obtained) clusters and therefore enables finding the global structure of the network. It tries to find such a partition of the vertices/units in the network where an appropriate model (a small network we obtain by shrinking all clusters of the partitions) describes the initial network’s globla (overall) structure. Recently, a lot of attention has been devoted to the analysis of multilevel and temporal networks. When analysing multilevel networks, we simultaneously study the ties among units from at least two levels (the ties both within and between levels). Often the first level represents individuals and the second organisations. We will use the term “linked networks” for both types of network, that is, multilevel and temporal networks (as networks measured at several time points). Numerous deterministic and stochastic methods have been developed for blockmodeling. Nevertheless, most of them cannot be used for blockmodeling multilevel and temporal networks or so-called linked networks. There exist versions of stochastic blockmodeling for temporal networks and we have developed methods for generalised blockmodeling of multilevel networks, which can also be used for blockmodeling other linked networks. However, the first are not applicable to multilevel networks and do not support the use of pre-specified blockmodeling, while the others in their current development stage are only appropriate for relatively small networks (up to 100 units in each network in the case of only two networks), in part also due to the use of a non-tailored optimisation procedure. With our approach, there is also a need to improve the way different parts of the solution are weighted. PROBLEM DEFINITION: Currently, there is no method for blockmodeling linked networks that would enable the blockmodeling of larger linked networks (with at least several hundred vertices/units) within a reasonable time. This is the problem we would like to solve and by using methods that would incorporate at least some elements of generalised blockmodeling. In addition, we will study which models, especially for so-called linking networks, namely, parts of the linked networks that represent ties among individual onemode networks, are appropriate for different kinds of linked networks (multilevel, temporal, temporal multilevel). RESEARCH OBJECTIVES: The project has two main objectives: (i) to improve the optimisation method for generalised blockmodeling for use in blockmodeling linked networks; and (ii) to adapt faster blockmodeling approaches (e.g. stochastic blockmodeling) for blockmodeling linked networks with selected elements of generalised blockmodeling. An additional objective is to apply the developed methods to empirical networks in the field of collaboration in science (e.g. collaboration among researchers through time and collaboration among researchers and their institutions) and supply the appropriate findings. Within the project, we will also research local mechanisms that lead towards a certain global (blockmodeling) network structure or change the global structure and enable the generating of random networks with a given blockmodeling structure. EXECUTION: For most of its duration, the project will be split into two main branches, each one dealing with its own core objective (that is, either improving optimisation methods or adapting faster approaches to blockmodeling for linked networks). Each branch will be led by one institution (IMFM or FSS). The work plan is actually similar for both. The initial literature review will be followed by the design of new algorithms or methods, which will then go through testing phases (including applications), improvements and, if needed, also return to design phase developed into final methods in line with the objective of the individual branch. All developed methods will also be applied to networks of collaboration in science.