A Sumarização Automática de Textos tem considerável importância nas tarefas de localização e utilização de conteúdo relevante em meio à quantidade enorme de informação disponível atualmente em meio digital. Nessa área, procura-se desenvolver técnicas que possibilitem obter o conteúdo mais relevante de documentos, de maneira condensada, sem alterar seu significado original, e com mínima intervenção humana. O objetivo deste trabalho de mestrado foi investigar de que maneira conceitos desenvolvidos na área de Redes Complexas podem ser aplicados à Sumarização Automática de Textos, mais especificamente à sumarização extrativa. Embora grande parte das pesquisas em sumarização tenha se voltado para a utilização de técnicas extrativas, ainda é possível melhorar o nível de informatividade dos extratos gerados automaticamente. Neste trabalho, textos foram representados como redes, das quais foram extraídas medidas tradicionalmente utilizadas na caracterização de redes complexas (por exemplo, coeficiente de aglomeração, grau hierárquico e índice de localidade), com o intuito de fornecer subsídios à seleção das sentenças mais significativas de um texto. Essas redes são formadas pelas sentenças (representadas pelos vértices) de um determinado texto, juntamente com as repetições (representadas pelas arestas) de substantivos entre sentenças após lematização. Cada método de sumarização proposto foi aplicado no córpus TeMário, de textos jornalísticos em português, e em córpus das conferências DUC, de textos jornalísticos em inglês. A avaliação desse estudo foi feita por meio da realização de quatro experimentos, fazendo-se uso de métodos de avaliação automática (Rouge-1 e Precisão/Cobertura de sentenças) e comparando-se os resultados com os de outros sistemas de sumarização extrativa. Os melhores sumarizadores propostos referem-se aos seguintes conceitos: d-anel, grau, k-núcleo e caminho mínimo. Foram obtidos resultados comparáveis aos dos melhores métodos de sumarização já propostos para o português, enquanto que, para o inglês, os resultados são menos expressivos. / Automatic Text Summarization has considerably importance in tasks such as finding and using relevant content in the enormous amount of information available nowadays in digital media. The focus in this field is on the development of techniques that allow someone to obtain the most relevant content of documents, in a condensed way, preserving the original meaning and with little (or even none) human help. The purpose of this MSc project was to investigate a way of applying concepts borrowed from the studies of Complex Networks to the Automatic Text Summarization field, specifically to the task of extractive summarization. Although the majority of works in summarization have focused on extractive techniques, it is still possible to obtain better levels of informativity in extracts automatically generated. In this work, texts were represented as networks, from which the most significant sentences were selected through the use of ranking algorithms. Such networks are obtained from a text in the following manner: the sentences are represented as nodes, and an edge between two nodes is created if there is at least one repetition of a noun in both sentences, after the lemmatization step. Measurements typically employed in the characterization of complex networks, such as clustering coefficient, hierarchical degree and locality index, were used on the basis of the process of node (sentence) selection in order to build an extract. Each summarization technique proposed was applied to the TeMário corpus, which comprises newspaper articles in Portuguese, and to the DUC corpora, which comprises newspaper articles in English. Four evaluation experiments were carried out, by means of automatic evaluation measurements (Rouge-1 and sentence Precision/Recall) and comparison with the results obtained by other extractive summarization systems. The best summarizers are the ones based on the following concepts: d-ring, degree, k-core and shortest path. Performances comparable to the best summarization systems for Portuguese were achieved, whilst the results are less significant for English.

L'étude de l'influence sur les réseaux sociaux et en particulier Twitter est un sujet de recherche intense. La détection des utilisateurs influents dans un réseau est une clé de succès pour parvenir à une diffusion d'information à large échelle et à faible coût, ce qui s'avère très utile dans le marketing ou les campagnes politiques. Dans cette thèse, nous proposons une nouvelle approche qui tient compte de la variété des relations entre utilisateurs afin d'estimer l'influence dans les réseaux sociaux tels que Twitter. Nous modélisons Twitter comme un réseau multiplexe hétérogène où les utilisateurs, les tweets et les objets représentent les noeuds, et les liens modélisent les différentes relations entre eux (par exemple, retweets, mentions et réponses). Le PageRank multiplexe est appliqué aux données issues de deux corpus relatifs au domaine politique pour classer les candidats selon leur influence. Si le classement des candidats reflète la réalité, les scores de PageRank multiplexe sont difficiles à interpréter car ils sont très proches les uns des autres.Ainsi, nous voulons aller au-delà d'une mesure quantitative et nous explorons comment les différentes relations entre les noeuds du réseau peuvent déterminer un degré d'influence pondéré par une estimation de la crédibilité. Nous proposons une approche, TwitBelief, basée sur la règle de combinaison conjonctive de la théorie des fonctions de croyance qui permet de combiner différents types de relations tout en exprimant l’incertitude sur leur importance relative. Nous expérimentons TwitBelief sur une grande quantité de données collectées lors des élections européennes de 2014 et de l'élection présidentielle française de 2017 et nous déterminons les candidats les plus influents. Les résultats montrent que notre modèle est suffisamment flexible pour répondre aux besoins des spécialistes en sciences sociales et que l'utilisation de la théorie des fonctions de croyances est pertinente pour traiter des relations multiples. Nous évaluons également l'approche sur l'ensemble de données CLEF RepLab 2014 et montrons que notre approche conduit à des résultats significatifs. Nous proposons aussi deux extensions de TwitBelief traitant le contenu des tweets. La première est l'estimation de la polarisation de l'influence sur le réseau Twitter en utilisant l'analyse des sentiments avec l'algorithme des forêts d'arbres décisionnels. La deuxième extension est la catégorisation des styles de communication dans Twitter, il s'agit de déterminer si le style de communication des utilisateurs de Twitter est informatif, interactif ou équilibré. / Influence in complex networks and in particular Twitter has become recently a hot research topic. Detecting most influential users leads to reach a large-scale information diffusion area at low cost, something very useful in marketing or political campaigns. In this thesis, we propose a new approach that considers the several relations between users in order to assess influence in complex networks such as Twitter. We model Twitter as a multiplex heterogeneous network where users, tweets and objects are represented by nodes, and links model the different relations between them (e.g., retweets, mentions, and replies).The multiplex PageRank is applied to data from two datasets in the political field to rank candidates according to their influence. Even though the candidates' ranking reflects the reality, the multiplex PageRank scores are difficult to interpret because they are very close to each other.Thus, we want to go beyond a quantitative measure and we explore how relations between nodes in the network could reveal about the influence and propose TwitBelief, an approach to assess weighted influence of a certain node. This is based on the conjunctive combination rule from the belief functions theory that allow to combine different types of relations while expressing uncertainty about their importance weights. We experiment TwitBelief on a large amount of data gathered from Twitter during the European Elections 2014 and the French 2017 elections and deduce top influential candidates. The results show that our model is flexible enough to consider multiple interactions combination according to social scientists needs or requirements and that the numerical results of the belief theory are accurate. We also evaluate the approach over the CLEF RepLab 2014 data set and show that our approach leads to quite interesting results. We also propose two extensions of TwitBelief in order to consider the tweets content. The first is the estimation of polarized influence in Twitter network. In this extension, sentiment analysis of the tweets with the algorithm of forest decision trees allows to determine the influence polarity. The second extension is the categorization of communication styles in Twitter, it determines whether the communication style of Twitter users is informative, interactive or balanced.

There any many different aspects in natural languages and their related dynamics that have been studied. In the case of languages, some quantitative analyses have been done by using stochastic models. Furthermore, natural languages can be understood as complex systems. Thus, there is a possibility to use set of tools development to analyse complex networks, which are computationally represented by graphs, also to analyse natural languages. Furthermore, these tools can be used to represent and analyse some related dynamics taking place on the networks. Observe that knowledge is intrinsically related to language, because language is the vehicle used by humans beings to transmit dicoveries, and the language itself is also a type of knowledge. This thesis is divided into two types of analyses: (i) texts and (II) dynamical aspects. In the first part, we proposed networks representations of text in different scales analyses, starting from the analysis of writing style considering word adjacency networks (co-occurence) to understand local patterns of words, to a mesoscopic representation, which is created from chunks of text and grasps information of the unfolding of the story. In the second part, we considered the structure and dynamics related to knowledge and language, in this case, starting from the larger scale, in which we studied the connectivity between applied and theoretical physics. In the following, we simulated the knowledge acquisition by researchers in a multi-agent dynamics and an intelligent machine that solves problems, which is represented by a network. At the smallest considered scale, we simulate the transmission of networks. This transmission considers the data as a series of organized symbols that is obtained from a dynamics. In order to improve the speed of transmission, the series can be compacted. For that, we considered the information theory and Huffman code. The proposed network-based approaches were found to be suitable to deal with the employed analysis for all of the tested scales. / Existem diversos aspectos das linguagens naturais e de dinâmicas relacionadas que estão sendo estudadas. No caso das línguas, algumas análises quantitativas foram feitas usando modelos estocásticos. Ademais, linguagens naturais podem ser entendidas como sistemas complexos. Para analisar linguagens naturais, existe a possibilidade de utilizar o conjunto de ferramentas que já foram desenvolvidas para analisar redes complexas, que são representadas computacionalmente. Além disso, tais ferramentas podem ser utilizadas para representar e analisar algumas dinâmicas relacionadas a redes complexas. Observe que o conhecimento está intrinsecamente relacionado à linguagem, pois a linguagem é o veículo usado para transmitir novas descobertas, sendo que a própria linguagem também é um tipo de conhecimento. Esta tese é dividida em dois tipos de análise : (i) textos e (ii) aspectos dinâmicos. Na primeira parte foram propostas representações de redes de texto em diferentes escalas de análise. A partir da análise do estilo de escrita, considerando redes de adjacência de palavras (co-ocorrência) para entender padrões locais de palavras, até uma representação mesoscópica, que é criada a partir de pedaços de texto e que representa informações do texto de acordo com o desenrolar da história. Na segunda parte, foram consideradas a estrutura e dinâmica relacionadas ao conhecimento e à linguagem. Neste caso, partiu-se da escala maior, com a qual estudamos a conectividade entre física aplicada e física teórica. A seguir, simulou-se a aquisição de conhecimento por pesquisadores em uma dinâmica multi-agente e uma máquina inteligente que resolve problemas, que é representada por uma rede. Como a menor escala considerada, foi simulada a transmissão de redes. Essa transmissão considera os dados como uma série de símbolos organizados que são obtidos a partir de uma dinâmica. Para melhorar a velocidade de transmissão, a série pode ser compactada. Para tanto, foi utilizada a teoria da informação e o código de Huffman. As propostas de abordagens baseadas em rede foram consideradas adequadas para lidar com a análise empregada, em todas as escalas testadas.

<p>Networks are all around us, all the time. From the biochemistry of our cells to the web of friendships across the planet. From the circuitry of modern electronics to chains of historical events. A network is the result of the forces that shaped it. Thus the principles of network formation can be, to some extent, deciphered from the network itself. All such information comprises the structure of the network. The study of network structure is the core of modern network science. This thesis centres around three aspects of network structure: What kinds of network structures are there and how can they be measured? How can we build models for network formation that give the structure of networks in the real world? How does the network structure affect dynamical systems confined to the networks? These questions are discussed using a variety of statistical, analytical and modelling techniques developed by physicists, mathematicians, biologists, chemists, psychologists, sociologists and anthropologists. My own research touches all three questions. In this thesis I present works trying to answer: What is the best way to protect a network against sinister attacks? How do groups form in friendship networks? Where do traffic jams appear in a communication network? How is cellular metabolism organised? How do Swedes flirt on the Internet? . . . and many other questions.</p>

Complex network theory provides an elegant and powerful framework to statistically investigate the topology of local and long range dynamical interrelationships, i.e., teleconnections, in the climate system. Employing a refined methodology relying on linear and nonlinear measures of time series analysis, the intricate correlation structure within a multivariate climatological data set is cast into network form. Within this graph theoretical framework, vertices are identified with grid points taken from the data set representing a region on the the Earth's surface, and edges correspond to strong statistical interrelationships between the dynamics on pairs of grid points. The resulting climate networks are neither perfectly regular nor completely random, but display the intriguing and nontrivial characteristics of complexity commonly found in real world networks such as the internet, citation and acquaintance networks, food webs and cortical networks in the mammalian brain. Among other interesting properties, climate networks exhibit the "small-world" effect and possess a broad degree distribution with dominating super-nodes as well as a pronounced community structure. We have performed an extensive and detailed graph theoretical analysis of climate networks on the global topological scale focussing on the flow and centrality measure betweenness which is locally defined at each vertex, but includes global topological information by relying on the distribution of shortest paths between all pairs of vertices in the network. The betweenness centrality field reveals a rich internal structure in complex climate networks constructed from reanalysis and atmosphere-ocean coupled general circulation model (AOGCM) surface air temperature data. Our novel approach uncovers an elaborately woven meta-network of highly localized channels of strong dynamical information flow, that we relate to global surface ocean currents and dub the backbone of the climate network in analogy to the homonymous data highways of the internet. This finding points to a major role of the oceanic surface circulation in coupling and stabilizing the global temperature field in the long term mean (140 years for the model run and 60 years for reanalysis data). Carefully comparing the backbone structures detected in climate networks constructed using linear Pearson correlation and nonlinear mutual information, we argue that the high sensitivity of betweenness with respect to small changes in network structure may allow to detect the footprints of strongly nonlinear physical interactions in the climate system. The results presented in this thesis are thoroughly founded and substantiated using a hierarchy of statistical significance tests on the level of time series and networks, i.e., by tests based on time series surrogates as well as network surrogates. This is particularly relevant when working with real world data. Specifically, we developed new types of network surrogates to include the additional constraints imposed by the spatial embedding of vertices in a climate network. Our methodology is of potential interest for a broad audience within the physics community and various applied fields, because it is universal in the sense of being valid for any spatially extended dynamical system. It can help to understand the localized flow of dynamical information in any such system by combining multivariate time series analysis, a complex network approach and the information flow measure betweenness centrality. Possible fields of application include fluid dynamics (turbulence), plasma physics and biological physics (population models, neural networks, cell models). Furthermore, the climate network approach is equally relevant for experimental data as well as model simulations and hence introduces a novel perspective on model evaluation and data driven model building. Our work is timely in the context of the current debate on climate change within the scientific community, since it allows to assess from a new perspective the regional vulnerability and stability of the climate system while relying on global and not only on regional knowledge. The methodology developed in this thesis hence has the potential to substantially contribute to the understanding of the local effect of extreme events and tipping points in the earth system within a holistic global framework. / Die Theorie komplexer Netzwerke bietet einen eleganten Rahmen zur statistischen Untersuchung der Topologie lokaler und langreichweitiger dynamischer Zusammenhänge (Telekonnektionen) im Klimasystem. Unter Verwendung einer verfeinerten, auf linearen und nichtlinearen Korrelationsmaßen der Zeitreihenanalyse beruhenden Netzwerkkonstruktionsmethode, bilden wir die komplexe Korrelationsstruktur eines multivariaten klimatologischen Datensatzes auf ein Netzwerk ab. Dabei identifizieren wir die Knoten des Netzwerkes mit den Gitterpunkten des zugrundeliegenden Datensatzes, während wir Paare von besonders stark korrelierten Knoten als Kanten auffassen. Die resultierenden Klimanetzwerke zeigen weder die perfekte Regularität eines Kristallgitters, noch eine vollkommen zufällige Topologie. Vielmehr weisen sie faszinierende und nichttriviale Eigenschaften auf, die charakteristisch für natürlich gewachsene Netzwerke wie z.B. das Internet, Zitations- und Bekanntschaftsnetzwerke, Nahrungsnetze und kortikale Netzwerke im Säugetiergehirn sind. Besonders erwähnenswert ist, dass in Klimanetzwerken das Kleine-Welt-Phänomen auftritt. Desweiteren besitzen sie eine breite Gradverteilung, werden von Superknoten mit sehr vielen Nachbarn dominiert, und bilden schließlich regional wohldefinierte Untergruppen von intern dicht vernetzten Knoten aus. Im Rahmen dieser Arbeit wurde eine detaillierte, graphentheoretische Analyse von Klimanetzwerken auf der globalen topologischen Skala durchgeführt, wobei wir uns auf das Netzwerkfluss- und Zentralitätsmaß Betweenness konzentrierten. Betweenness ist zwar lokal an jedem Knoten definiert, enthält aber trotzdem Informationen über die globale Netzwerktopologie. Dies beruht darauf, dass die Verteilung kürzester Pfade zwischen allen möglichen Paaren von Knoten in die Berechnung des Maßes eingeht. Das Betweennessfeld zeigt reichhaltige und zuvor verborgene Strukturen in aus Reanalyse- und Modelldaten der erdoberflächennahen Lufttemperatur gewonnenen Klimanetzen. Das durch unseren neuartigen Ansatz enthüllte Metanetzwerk, bestehend aus hochlokalisierten Kanälen stark gebündelten Informationsflusses, bringen wir mit der Oberflächenzirkulation des Weltozeans in Verbindung. In Analogie mit den gleichnamigen Datenautobahnen des Internets nennen wir dieses Metanetzwerk den Backbone des Klimanetzwerks. Unsere Ergebnisse deuten insgesamt darauf hin, dass Meeresoberflächenströmungen einen wichtigen Beitrag zur Kopplung und Stabilisierung des globalen Oberflächenlufttemperaturfeldes leisten. Wir zeigen weiterhin, dass die hohe Sensitivität des Betweennessmaßes hinsichtlich kleiner Änderungen der Netzwerktopologie die Detektion stark nichtlinearer physikalischer Wechselwirkungen im Klimasystem ermöglichen könnte. Die in dieser Arbeit vorgestellten Ergebnisse wurden mithilfe statistischer Signifikanztests auf der Zeitreihen- und Netzwerkebene gründlich auf ihre Robustheit geprüft. In Anbetracht fehlerbehafteter Daten und komplexer statistischer Zusammenhänge zwischen verschiedenen Netzwerkmaßen ist diese Vorgehensweise besonders wichtig. Weiterhin ist die Entwicklung neuer, allgemein anwendbarer Surrogate für räumlich eingebettete Netzwerke hervorzuheben, die die Berücksichtigung spezieller Klimanetzwerkeigenschaften wie z.B. der Wahrscheinlichkeitsverteilung der Kantenlängen erlauben. Unsere Methode ist universell, weil sie zum Verständnis des lokalisierten Informationsflusses in allen räumlich ausgedehnten, dynamischen Systemen beitragen kann. Deshalb ist sie innerhalb der Physik und anderer angewandter Wissenschaften von potentiell breitem Interesse. Mögliche Anwendungen könnten sich z.B. in der Fluiddynamik (Turbulenz), der Plasmaphysik und der Biophysik (Populationsmodelle, neuronale Netzwerke und Zellmodelle) finden. Darüber hinaus ist der Netzwerkansatz für experimentelle Daten sowie Modellsimulationen gültig, und eröffnet folglich neue Perspektiven für Modellevaluation und datengetriebene Modellierung. Im Rahmen der aktuellen Klimawandeldebatte stellen Klimanetzwerke einen neuartigen Satz von Analysemethoden zur Verfügung, der die Evaluation der lokalen Vulnerabilität und Stabilität des Klimasystems unter Berücksichtigung globaler Randbedingungen ermöglicht. Die in dieser Arbeit entwickelten und untersuchten Methoden könnten folglich in der Zukunft, innerhalb eines holistisch-globalen Ansatzes, zum Verständnis der lokalen Auswirkungen von Extremereignissen und Kipppunkten im Erdsystem beitragen.

Complex networks are employed as a mathematical description of complex systems in many different fields, ranging from biology to sociology, economy and ecology. Dynamical processes in these systems often display phase transitions, where the dynamics of the system changes qualitatively. In combination with these phase transitions certain components of the system might irretrievably go extinct. In this case, we talk about absorbing transitions. Developing mathematical tools, which allow for an analysis and prediction of the observed phase transitions is crucial for the investigation of complex networks. In this thesis, we investigate absorbing transitions in dynamical networks, where a certain amount of diversity is lost. In some real-world examples, e.g. in the evolution of human societies or of ecological systems, it is desirable to maintain a high degree of diversity, whereas in others, e.g. in epidemic spreading, the diversity of diseases is worthwhile to confine. An understanding of the underlying mechanisms for emergence and persistence of diversity in complex systems is therefore essential. Within the scope of two different network models, we develop an analytical approach, which can be used to estimate the prerequisites for diversity. In the first part, we study a model for opinion formation in human societies. In this model, regimes of low diversity and regimes of high diversity are separated by a fragmentation transition, where the network breaks into disconnected components, corresponding to different opinions. We propose an approach for the estimation of the fragmentation point. The approach is based on a linear stability analysis of the fragmented state close to the phase transition and yields much more accurate results compared to conventional methods. In the second part, we study a model for the formation of complex food webs. We calculate and analyze coexistence conditions for several types of species in ecological communities. To this aim, we employ an approach which involves an iterative stability analysis of the equilibrium with respect to the arrival of a new species. The proposed formalism allows for a direct calculation of coexistence ranges and thus facilitates a systematic analysis of persistence conditions for food webs. In summary, we present a general mathematical framework for the calculation of absorbing phase transitions in complex networks, which is based on concepts from percolation theory. While the specific implementation of the formalism differs from model to model, the basic principle remains applicable to a wide range of different models.

Complex systems can often be modelled as networks, in which their basic units are represented by abstract nodes and the interactions among them by abstract links. This network of interactions is the key to understanding emergent collective phenomena in such systems. In most cases, it is an adaptive network, which is defined by a feedback loop between the local dynamics of the individual units and the dynamical changes of the network structure itself. This feedback loop gives rise to many novel phenomena. Adaptive networks are a promising concept for the investigation of collective phenomena in different systems. However, they also present a challenge to existing modelling approaches and analytical descriptions due to the tight coupling between local and topological degrees of freedom. In this thesis, I present a simple rule-based framework for the investigation of adaptive networks, using which a wide range of collective phenomena can be modelled and analysed from a common perspective. In this framework, a microscopic model is defined by the local interaction rules of small network motifs, which can be implemented in stochastic simulations straightforwardly. Moreover, an approximate emergent-level description in terms of macroscopic variables can be derived from the microscopic rules, which we use to analyse the system\'s collective and long-term behaviour by applying tools from dynamical systems theory. We discuss three adaptive-network models for different collective phenomena within our common framework. First, we propose a novel approach to collective motion in insect swarms, in which we consider the insects\' adaptive interaction network instead of explicitly tracking their positions and velocities. We capture the experimentally observed onset of collective motion qualitatively in terms of a bifurcation in this non-spatial model. We find that three-body interactions are an essential ingredient for collective motion to emerge. Moreover, we show what minimal microscopic interaction rules determine whether the transition to collective motion is continuous or discontinuous. Second, we consider a model of opinion formation in groups of individuals, where we focus on the effect of directed links in adaptive networks. Extending the adaptive voter model to directed networks, we find a novel fragmentation mechanism, by which the network breaks into distinct components of opposing agents. This fragmentation is mediated by the formation of self-stabilizing structures in the network, which do not occur in the undirected case. We find that they are related to degree correlations stemming from the interplay of link directionality and adaptive topological change. Third, we discuss a model for the evolution of cooperation among self-interested agents, in which the adaptive nature of their interaction network gives rise to a novel dynamical mechanism promoting cooperation. We show that even full cooperation can be achieved asymptotically if the networks\' adaptive response to the agents\' dynamics is sufficiently fast.

Telechelic associating polymer networks consist of polymer chains terminated by endgroups that have a different chemical composition than the polymer backbone. When dissolved in a solution, the endgroups cluster together to form aggregates. At low temperature, a strongly connected reversible network is formed and the system behaves like a gel. Telechelic networks are of interest since they are representative for biopolymer networks (e.g. F-actin) and are widely used in medical applications (e.g. hydrogels for tissue engineering, wound dressings) and consumer products (e.g. contact lenses, paint thickeners). In this thesis such systems are studied by means of a molecular dynamics/Monte Carlo simulation. At first, the system in rest is studied by means of graph theory. The changes in network topology upon cooling to the gel state, are characterized. Hereto an extensive study of the eigenvalue spectrum of the gel network is performed. As a result, an in-depth investigation of the eigenvalue spectra for spatial ER, scale-free, and small-world networks is carried out. Next, the gel under the application of a constant shear is studied, with a focus on shear banding and the changes in topology under shear. Finally, the relation between the gel transition and percolation is discussed.

A large number of complex systems can be modelled as networks of interacting units. From a mathematical point of view the topology of such systems can be represented as graphs of which the nodes represent individual elements of the system and the edges interactions or relations between them. In recent years networks have become a principal tool for analyzing complex systems in many different fields. This thesis introduces an information theoretic approach for finding characteristic connectivity patterns of networks, also called network motifs. Network motifs are sometimes also referred to as basic building blocks of complex networks. Many real world networks contain a statistically surprising number of certain subgraph patterns called network motifs. In biological and technological networks motifs are thought to contribute to the overall function of the network by performing modular tasks such as information processing. Therefore, methods for identifying network motifs are of great scientific interest. In the prevalent approach to motif analysis network motifs are defined to be subgraphs that occur significantly more often in a network when compared to a null model that preserves certain features of the network. However, defining appropriate null models and sampling these has proven to be challenging. This thesis introduces an alternative approach to motif analysis which looks at motifs as regularities of a network that can be exploited to obtain a more efficient representation of the network. The approach is based on finding a subgraph cover that represents the network using minimal total information. Here, a subgraph cover is a set of subgraphs such that every edge of the graph is contained in at least one subgraph in the cover while the total information of a subgraph cover is the information required to specify the connectivity patterns occurring in the cover together with their position in the graph. The thesis also studies the connection between motif analysis and random graph models for networks. Developing random graph models that incorporate high densities of triangles and other motifs has long been a goal of network research. In recent years, two such model have been proposed . However, their applications have remained limited because of the lack of a method for fitting such models to networks. In this thesis, we address this problem by showing that these models can be formulated as ensembles of subgraph covers and that the total information optimal subgraph covers can be used to match networks with such models. Moreover, these models can be solved analytically for many of their properties allowing for more accurate modelling of networks in general. Finally, the thesis also analyzes the problem of finding a total information optimal subgraph cover with respect to its computational complexity. The problem turns out to be NP-hard hence, we propose a greedy heuristic for it. Empirical results for several real world networks from different fields are presented. In order to test the presented algorithm we also consider some synthetic networks with predetermined motif structure.

ARAÚJO, Eduardo Barbosa. Scientific Collaboration Networks from Lattes Database: Topology, Dynamics and Gender Statistics. 2016. 88 f. Tese (Doutorado em Física) - Programa de Pós-Graduação em Física, Departamento de Física, Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Edvander Pires (edvanderpires@gmail.com) on 2016-07-19T15:58:54Z No. of bitstreams: 1 2016_tese_ebaraujo.pdf: 3600069 bytes, checksum: a78e83ffda97c499e589b405da4da3c8 (MD5) / Approved for entry into archive by Edvander Pires (edvanderpires@gmail.com) on 2016-07-19T15:59:07Z (GMT) No. of bitstreams: 1 2016_tese_ebaraujo.pdf: 3600069 bytes, checksum: a78e83ffda97c499e589b405da4da3c8 (MD5) / Made available in DSpace on 2016-07-19T15:59:07Z (GMT). No. of bitstreams: 1 2016_tese_ebaraujo.pdf: 3600069 bytes, checksum: a78e83ffda97c499e589b405da4da3c8 (MD5) Previous issue date: 2016 / Understanding the dynamics of research production and collaboration may reveal better strategies for scientific careers, academic institutions and funding agencies. Here we propose the use of a large and multidisciplinary database of scientific curricula in Brazil, namely, the Lattes Platform, to study patterns of scientific production and collaboration. Detailed information about publications and researchers is available in this database. Individual curricula are submitted by the researchers themselves so that co-authorship is unambiguous. Researchers can be evaluated by scientific productivity, geographical location and field of expertise. Our results show that the collaboration network is growing exponentially for the last three decades, with a distribution of number of collaborators per researcher that approaches a power-law as the network gets older. Moreover, both the distributions of number of collaborators and production per researcher obey power-law behaviors, regardless of the geographical location or field, suggesting that the same universal mechanism might be responsible for network growth and productivity. We also show that the collaboration network under investigation displays a typical assortative mixing behavior, where teeming researchers (i.e., with high degree) tend to collaborate with others alike. Moreover, we discover that on average men prefer collaborating with other men than with women, while women are more egalitarian. This is consistently observed over all fields and essentially independent on the number of collaborators of the researcher. The solely exception is for engineering, where clearly this gender bias is less pronounced, when the number of collaborators increases. We also find that the distribution of number of collaborators follows a power-law, with a cut-off that is gender dependent. This reflects the fact that on average men produce more papers andhave more collaborators than women. We also find that both genders display the same tendency towards interdisciplinary collaborations, except for Exact and Earth Sciences, where women having many collaborators are more open to interdisciplinary research. / Compreender a dinâmica de produção e colaboração em pesquisa pode revelar melhores estratégias para carreiras científicas, instituições acadêmicas e agências de fomento. Neste trabalho nós propomos o uso de uma grande e multidisciplinar base de currículos científicos brasileira, a Plataforma Lattes, para o estudo de padrões em pesquisa científica e colaborações. Esta base de dados inclui informações detalhadas acerca de publicações e pesquisadores. Currículos individuais são enviados pelos próprios pesquisadores de forma que a identificação de coautoria não é ambígua. Pesquisadores podem ser classificados por produção científica, localização geográfica e áreas de pesquisa. Nossos resultados mostram que a rede de colaborações científicas tem crescido exponencialmente nas últimas três décadas, com a distribuição do número de colaboradores por pesquisador se aproximando de uma lei de potência à medida que a rede evolui. Além disso, ambas a distribuição do número de colaboradores e a produção por pesquisador seguem o comportamento de leis de potência, independentemente da região ou áreas, sugerindo que um mesmo mecanismo universal pode ser responsável pelo crescimento da rede e pela produtividade dos pesquisadores. Também mostramos que as redes de colaboração investigadas apresentam um típico comportamento assortativo, no qual pesquisadores de alto nível (com muitos colaboradores) tendem a colaborador com outros semelhantes. Em seguida, mostramos que homens preferem colaborar com outros homens enquanto mulheres são mais igualitárias ao estabelecer suas colaborações. Isso é consistentemente observado em todas as áreas e é essencialmente independente do número de colaborações do pesquisador. A única exceção sendo a área de Engenharia, na qual este viés é claramente menos pronunciado para pesquisadores com muitas colaborações. Também mostramos que o número de colaborações segue o comportamento de leis de potência, com um cutoff dependente do gênero. Isso se reflete no fato de que em média mulheres produzem menos artigos e têm menos colaborações que homens. Também mostramos que ambos os gêneros exibem a mesma tendência quanto a colaborações interdisciplinares, exceto em Ciências Exatas e da Terra, nas quais mulheres tendo mais colaboradores são mais propensas a pesquisas interdisciplinares.