Ο στόχος αυτής της εργασίας είναι η μελέτη κάποιων μαθηματικών μεθόδων για τη μοντελοποίηση σε μπλοκ δικτύων με βάρη -- όπως μελετήθηκαν στην διδακτορική διατριβή του Ziberna (2007). Στο μεγαλύτερό τους μέρος, οι μέθοδοι της μοντελοποίησης σε μπλοκ είχαν αναπτυχθεί αρχικά μόνο για δυαδικά και προσημασμένα δίκτυα κυρίως από τους Doreian et al. (2005). Στην διατριβή του Ziberna (2007) συζητήθηκαν και αξιολογήθηκαν οι υπάρχουσες προσεγγίσεις και επεκτάθηκαν για την μοντελοποίηση σε μπλοκ δικτύων με βάρη. Για τις έμμεσες προσέγγισεις, σύμφωνα με τον γνωστό ορισμό της κανονικής ισοδυναμίας, ο Ziberna πρότεινε κάποιες σχετικές τροποποιήσεις. Αυτό έγινε επίσης με στόχο να βρεθούν οι καλύτερες μέθοδοι για τη μοντελοποίηση σε μπλοκ διαφορετικών τύπων δικτύων με βάρη και για την αναζήτηση των βέλτιστων λύσεων, που έχουν διαφορετικά χαρακτηριστικά (σύμφωνα με τους χρησιμοποιούμενους διαφορετικούς τύπους ισοδυναμίας, όπως θα δούμε στο Κεφάλαιο 2). Η μοντελοποίηση σε μπλοκ των δικτύων αποτελεί μέρος της ανάλυσης κοινωνικών δικτύων (Wasserman και Faust, 1994), που είναι περιοχή της Μαθηματικής Κοινωνιολογίας. Στη θεωρία αυτή, μια σύντομη ανασκόπηση της οποίας θα δώσουμε στο Κεφάλαιο 1, ένα (κοινωνικό) δίκτυο είναι ένα σύνολο μονάδων, οι οποίες συνδέονται μεταξύ τους με μια ή περισσότερες σχέσεις, που ορίζονται σε αυτές. Η μοντελοποίηση σε μπλοκ (κοινωνικών) δικτύων είναι μια μέθοδος για τη διαμέριση (ή ομαδοποίηση - clustering) των μονάδων ενός δικτύου και για τον προσδιορισμό της δομής των αθροιστικών σχέσεων μεταξύ των ομάδων, που σχηματίζονται από τις ομαδοποιημένες (διαμερισμένες) μονάδες. Έτσι, η μοντελοποίηση σε μπλοκ αναζητεί ομάδες ισοδύναμων μονάδων με βάση κάποια συγκεκριμένη έννοια ισοδυναμίας. Όπως παρατηρεί ο Doreian (1988), ``η ισοδυναμία έχει γίνει μια θεμελιώδης έννοια της ανάλυσης κοινωνικών δικτύων". Οι δύο ευρύτερα χρησιμοποιούμενες έννοιες ισοδυναμίας είναι η δομική και η κανονική ισοδυναμία. Για τους σκοπούς της παρούσας εργασίας, όπως θα δούμε στο Κεφάλαιο 2, οι μέθοδοι της μοντελοποίησης σε μπλοκ διαιρούνται στις έμμεσες και τις άμεσες προσεγγίσεις. Οι έμμεσες προσεγγίσεις υπολογίζουν αρχικά κάποιο μέτρο ομοιότητας ή ανομοιότητας μεταξύ των μονάδων ενός δικτύου με βάση ένα επιλεγμένο μέτρο ισοδυναμίας και χρησιμοποιούν έπειτα μια από τις κλασσικές τεχνικές ομαδοποίησης, για να προσδιορίσουν τις ομάδες των μονάδων. Από την άλλη μεριά, οι άμεσες προσεγγίσεις αναζητούν άμεσα μια διαμέριση, η οποία ταιριάζει καλύτερα στην επιλεγμένη ισοδυναμία και η οποία μετράται σύμφωνα με μια επιλεγμένη συνάρτηση κριτηρίου (Batagelj, 1992). Η μέθοδος της γενικευμένης μοντελοποίησης σε μπλοκ βασίζεται στην άμεση προσέγγιση. Όταν συγκρίνεται με άλλες άμεσες προσεγγίσεις, η κύρια δύναμή της είναι η προσαρμοστικότητά της. Μπορεί να χρησιμοποιηθεί για να πραγματοποιήσει κάποια μοντελοποίηση σε μπλοκ σύμφωνα με διαφορετικούς τύπους ισοδυναμίας, συμπεριλαμβανομένης και της γενικευμένης ισοδυναμίας. Η γενικευμένη ισοδυναμία δεν είναι ένας συγκεκριμένος τύπος ισοδυναμίας, αλλά περισσότερο μια έννοια για την κατασκευή ``ειδικών" ισοδυναμιών. Ορίζεται σύμφωνα με έναν προηγούμενο καθορισμό των επιτρεπόμενων τύπων συνδέσεων μεταξύ των ομάδων και μεταξύ μονάδων μέσα στις ομάδες. Πάντως, ενώ η γενικευμένη μοντελοποίηση σε μπλοκ αρχικά είχε αναπτυχθεί για δυαδικά και προσημασμένα δίκτυα, ο Ziberna (2007) ήταν ο πρώτος που την μελέτησε για δίκτυα με βάρη. Για το σκοπό αυτό, ο Ziberna εισήγαγε κάποιους νέους τύπους μπλοκ, που είναι κατάλληλοι για δίκτυα με βάρη. Τα κοινά χαρακτηριστικά όλων των προσεγγίσεων γενικευμένης μοντελοποίησης σε μπλοκ, εκτός από την κοινή βασική συνάρτηση κριτηρίου, περιλαμβάνουν την δυνατότητα προσδιορισμού της επιθυμητής λύσης είτε μέσω ενός τύπου ισοδυναμίας (που στη συνέχεια μεταφράζεται στους επιτρεπόμενους τύπους μπλοκ) ή μέσω κάποιας γενικευμένης ισοδυναμίας (η οποία ορίζεται άμεσα από τους επιτρεπόμενους τύπους μπλοκ ή, ακόμα ακριβέστερα, από το επιθυμητό μοντέλο των μπλοκ). Μια τέτοια έννοια ισοδυναμίας είναι η f-κανονική ισοδυναμία για δίκτυα με βάρη, η οποία αντιστοιχεί στην κανονική ισοδυναμία για τα δυαδικά ή προσημασμένα δίκτυα. Επιπλέον, θα μελετήσουμε στην εργασία αυτή κάποιους αλγόριθμους, που υλοποιούν τους υπολογισμούς για συγκεκριμένες μεθόδους μοντελοποίησης σε μπλοκ. Έτσι, για τις έμμεσες προσεγγίσεις, θα χρησιμοποιήσουμε τους αλγόριθμους REGE για τον υπολογισμό των ομοιοτήτων ή ανομοιοτήτων κάτω από συνθήκες κανονικής ισοδυναμίας. Στο Κεφάλαιο 3, όπου βρίσκεται ο πυρήνας της εργασίας, αναπτύσσονται οι μέθοδοι της γενικευμένης μοντελοποίησης σε μπλοκ δικτύων με βάρη. Αυτές οι προσεγγίσεις είναι οι εξής: η μοντελοποίηση σε μπλοκ με βάρη, η ομοιογενής μοντελοποίηση σε μπλοκ και η πεπλεγμένη μοντελοποίηση σε μπλοκ. Επιπλέον, ακολουθώντας τον Ziberna (2007), οι ιδέες των Batagelj και Ferligoj (2000) συζητώνται και αναπτύσσονται περαιτέρω για την περίπτωση της πεπλεγμένης μοντελοποίησης σε μπλοκ. Για να ενσωματώσει τις προτάσεις του για διάφορους τύπους μοντελοποίησης δικτύων με βάρη, ο Ziberna (2007) έχει αναπτύξει ένα σχετικό υπολογιστικό πακέτο, το blockmodeling, το οποίο είναι δομημένο πάνω στο προγραμματιστικό περιβάλλον R (R Development Core Team 2006). Αυτό θα παρουσιαστεί και θα συζητηθεί στο τέλος του Κεφαλαίου 3. Τέλος, στο Κεφάλαιο 4, θα εφαρμόσουμε τις μεθόδους της μοντελοποίησης σε μπλοκ σε διάφορα εμπειρικά και τεχνητά παραδείγματα. Ακόμα, στα παραδείγματα αυτά, οι προτεινόμενες προσεγγίσεις θα συγκριθούν ως προς τα θεωρητικά χαρακτηριστικά τους και την απόδοσή τους. / The aim of my work is to study and test approaches to the generalized blockmodeling of valued networks since so far the generalized blockmodeling approach has only been developed for binary and signed networks by Doreian et al. (2005). In addition, existing approaches that could be used for the blockmodeling of valued networks are discussed and evaluated. This is done with the aim to find the best methods or approaches for the blockmodeling of different types of valued networks1 in the search for optimal solutions with different characteristics. Generalized blockmodeling forms part of (social) network analysis. Simply put, a network is a set of units with one or more relations defined on them. Blockmodeling is a method for partitioning the units of a network and determining the pattern of relations among (obtained) clusters. Blockmodeling seeks clusters of equivalent units based on some notion of equivalence. The two most widely used equivalences are structural and regular equivalence. For the purpose of this dissertation, one of the most important divisions of blockmodeling approaches is into indirect and direct approaches. Indirect approaches first compute some measure of similarity or dissimilarity among the units of a network based on a selected measure of equivalence and then use one of the classical clustering techniques to uncover clusters of units, while direct approaches directly search for a partition that best fits the selected equivalence as measured by a selected criterion function. Generalized blockmodeling is based on the direct approach. When compared to other direct approaches, its main strength is its adaptability. It can be used to perform blockmodeling according to different types of equivalences, including generalized equivalence. Generalized equivalence is not a specific type of equivalence but more of a concept for building ‘custom’ equivalences. It is defined by specifying allowed types of connections between and within clusters. However, up till now generalized blockmodeling has only been developed for binary and signed networks. Here new approaches, by Ziberna, to the generalized blockmodeling of valued networks are discussed. However, as they can still be regarded as approaches to generalized blockmodeling as presented by Doreian et al. (2005) the same type of criterion function can be used. The most important differences between the approaches to generalized blockmodeling presented by Doreian et al. (2005) and those developed here is that the approaches presented by Doreian et al. (2005) can be applied to binary and signed networks, while those presented here can be applied to valued networks. To achieve that, new block types appropriate for valued networks are introduced by Ziberna. The common characteristics of all approaches to generalized blockmodeling are, in addition to the common basic criterion function, their ability to specify the desired solution either by a type of equivalence (which is then translated into allowed block types) or by generalized equivalence. Generalized equivalence is defined directly by the allowed block types or even more precisely by the desired blockmodel. In addition to generalized blockmodeling, other approaches to blockmodeling are reviewed (indirect blockmodeling and other direct approaches). For one family of algorithms that falls into the category of indirect approaches, the REGE algorithms for computing (dis)similarities in terms of regular equivalence, some modified versions are also presented. They and some other approaches are then tested on several empirical and constructed examples. The proposed approaches are compared based on their theoretical characteristics and their performance in the examples.

Στόχος της παρούσας διπλωματικής εργασίας είναι η μελέτη της ομαδοποίησης των προσημασμένων γράφων. / The main theme of this dissertation is the blockmodeling of signed graphs.

Between 1997 and 2009, 47 major defense acquisition programs experienced cost overruns of at least 15% or 30% over their current or original baseline estimates, respectively (GAO, 2011, p. 1). Known formally as a Nunn-McCurdy breach (GAO, 2011, p. 1), the reasons for this excessive growth are myriad, although nearly 70% of the cases identified engineering and design issues as a contributing factor (GAO, 2011, p. 5). Accordingly, Congress legislatively acknowledged the need for change in 2009 with the passage of the Weapon Systems Acquisition Reform Act (WSARA, 2009), which mandated additional rigor and accountability in early life cycle (or Pre-Milestone A) cost estimation. Consistent with this effort, the Department of Defense has recently required more system specification earlier in the life cycle, notably the submission of detailed architectural models, and this has created opportunities for new approaches. In this dissertation, I describe my effort to transform one such model (or view), namely the SV-3, into computational knowledge that can be leveraged in Pre-Milestone A cost estimation and risk analysis. The principal contribution of my work is Algorithm 3-a novel, network science-based method for estimating the cost of unforeseen architectural growth in defense programs. Specifically, using number theory, network science, simulation, and statistical analysis, I simultaneously find the best fitting probability mass functions and strengths of preferential attachment for an incoming subsystem's interfaces, and I apply blockmodeling to find the SV-3's globally optimal macrostructure. Leveraging these inputs, I use Monte Carlo simulation and the Constructive Systems Engineering Cost Model to estimate the systems engineering effort required to connect a new subsystem to the existing architecture. This effort is chronicled by the five articles given in Appendices A through C, and it is summarized in Chapter 2.In addition to Algorithm 3, there are several important, tangential outcomes of this work, including: an explicit connection between Model Based System Engineering and parametric cost modeling, a general procedure for organizations to improve the measurement reliability of their early life cycle cost estimates, and several exact and heuristic methods for the blockmodeling of one-, two-, and mixed-mode networks. More generally, this research highlights the benefits of applying network science to systems engineering, and it reinforces the value of viewing architectural models as computational objects.

In this thesis, I attempt to apply the network perspective to the study of corruption. First, I deal with current state of theory and research on corruption, which I find to be ignoring relations and interactions among offenders themselves. Then I review literature in the field of covert and criminal networks. The theoretical part of this thesis ends with brief descriptions of two major cases of political corruption in the Czech Republic - so called Nagy case and Rath case. In the methodological part, I introduce basic concepts of social network analysis as well as methods for positional analysis, especially the blockmodelling. In my research, I deal with exploratory analysis of both the aforementioned networks. Using proxy data, I analyse cohesion, centralization, centrality measures and cliques in these networks. Then I use conventional blockmodeling to search for roles and positions within these networks. My results suggest that both networks are dense and centralized with overlapping cliques contrary to other covert networks possibly accounting for their eventual disruption and failure. Positional analysis using varius methods such as CONCOR or different types of cluster analysis reveals a structure resembling the core-periphery model, which is supported by measuring coreness and finding a good...

Submitted by Luiz Felipe Barbosa (luiz.fbabreu2@ufpe.br) on 2015-03-09T12:49:55Z No. of bitstreams: 2 DISSERTAÇÃO Evandro José da Rocha e Silva.pdf: 1864754 bytes, checksum: 7f438607b1d1280050c14f8d4b2df203 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-09T12:49:55Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Evandro José da Rocha e Silva.pdf: 1864754 bytes, checksum: 7f438607b1d1280050c14f8d4b2df203 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014-02-25 / O reconhecimento de padrões é uma atividade frequente do ser humano. Entretanto muitas vezes não somos capazes de lidar com o volume de informações disponíveis. Para isso podemos recorrer às técnicas de Aprendizagem de Máquina, cujos algoritmos permitem a um computador aprender e classificar padrões de forma segura e veloz. Dentre os algoritmos que podem ser utilizados, existem aqueles que fazem parte dos sistemas de múltiplos classificadores. Nesses sistemas, vários classificadores trabalham em conjunto para a classificação dos padrões. O trabalho em conjunto pode ser realizado através da abordagem de seleção de classificadores. Neste trabalho foi desenvolvida uma metodologia para a construção de sistemas de múltiplos classificadores. Inicialmente o método usa os dados de treinamento para encontrar um mapa do agrupamento dos dados. Com isso, os dados de validação e teste pertencentes a cada grupo são encontrados. Então os classificadores são criados e treinados para cada grupo de dados. Através da abordagem de seleção de classificadores, o melhor classificador para cada agrupamento é encontrado. Os classificadores selecionados são usados para classificar os padrões não vistos que pertencem aos seus respectivos grupos. Foram implementadas duas versões do método proposto. A primeira, chamada BMGGAVS, conseguiu um bom desempenho, superando, na maioria das vezes, todos os outros métodos utilizados na comparação. A segunda versão do método, chamada BMG2GA, possui uma maior automatização. O BMG2GA não conseguiu resultados tão bons quanto os do BMGGAVS. Entretanto, em algumas situações, o BMG2GA conseguiu resultados próximos ou até melhores que os resultados de alguns dos métodos usados para comparação. Por causa desses últimos resultados, uma série de diretrizes são apresentadas para trabalhos futuros.

The questions for this study are: 1. What are networks? 2. How do networks work? These questions are answered by means of two different investigations. The first is chiefly theoretical and the second is primarily empirical. The theoretical investigation begins with an examination of four different concepts of networks used in social research: network as a perspective, network as a phenomenon, network as a research method and network as a method for development. The concept is then further investigated on three levels. On the first level, the parts of a network and the relationships between these parts are analysed. The second level focuses on the emergent properties of a network. The emergent properties refer to those irreducible features that make it a network, and that at the same time mark the difference between networks and other types of social entities (organizations, rituals etc.). Two such properties form the starting point for the examination, namely value-adding and diffusion. The third level of analysis places the network in relation to space and organization. This three level analysis is used throughout the thesis. In the empirical section, four cases of entrepreneurial networks are examined. The aim of the case studies is to identify the network and to study how the network works. What in the example is the network? How does the network work in the actual case? What does the network do? What properties can be assigned to the network and the way it works? Or, more comprehensively, from the examination of four cases of networks, what conclusions can be drawn about what networks are and how they function? From the case studies I have concluded that personal ties are fundamental to a network, and that the chains of production are a type of tie that may, but does not have to, occur when the network is activated in an entrepreneurial context. For the entrepreneurs and their enterprises, the social exchange has no value in itself, but if it can add value, for example as a lubricant in coordinating production chains, it fulfils an important purpose. I have also concluded that what makes an entrepreneurial network a network is not the coordination of production chains, but the personal relationships that manage these chains. Thus it is not the coordination itself, but the way of coordinating that is of importance. Networks can be found in structures of many different types of ties, but for the emergent properties to emerge there has to be a structure of personal ties at the core. I have assumed that a network is not a method or a perspective, but a social entity with certain properties. The investigation has provided support for this assumption. There is extensive research on SME networks, industrial districts and value-adding chains that shows that networks in production contexts form social constellations with their own distinctive features and ways of working. The relationship between networks and space is temporary, but not essential. Networks can be bound to places, but they do not have to be. An important structural difference between organizations and networks is that networks are formed of separate units that cooperate, while organizations form a single unit that may, but does not have to be characterized by cooperation. The most important conclusion from the comparison of organizations and networks is that these concepts together provide a better explanation of the case studies than either of the concepts alone. To understand and explain the complex social interplay that occurs in the case studies, it is a great advantage to use networks and organizations as concepts for different social entities with different properties and different ways of working.