In the last few years, large-scale experiments have generated genome-wide protein interaction networks for many organisms including Saccharomyces cerevisiae (baker's yeast), Caenorhabditis elegans (worm) and Drosophila melanogaster (fruit fly). In this thesis, we examine the vertex and edge betweenness centrality measures of these graphs. These measures capture how "central" a vertex or an edge is in the graph by considering the fraction of shortest paths that pass through that vertex or edge. Our primary observation is that the distribution of the vertex betweenness centrality follows a power law, but the distribution of the edge betweenness centrality has a Poisson-like distribution with a very sharp spike. To investigate this phenomenon, we generated random networks with degree distribution identical to those of the protein interaction networks. To our surprise, we found out that the random networks and the protein interaction networks had almost identical distribution of edge betweenness. We conjecture that the "Poisson-like" distribution of the edge betweenness centrality is the property of any graph whose degree distribution satisfies power law. / Master of Science

Individuals spend so many hours every day in their work spaces of different kinds. Different people have different needs in term of the quality of the space in which they are working. As a result it's important to provide a variety of spaces for people to be able to choose from and spend their work day in that space, or choose to transition in between spaces with different qualities during the day. This can positively affect employees' efficiency, productivity and even mental health. The main idea here is to design different spaces with different degrees of openness. These spaces start from being completely closed to completely open and just being defining by a single wall, roof or floor. And it also include every other degree of openness between these two states and having different combinations of walls, roofs and floors. / Master of Architecture / In Betweenness is about how to choose our position as designers when we are making changes into the earth to build livable spaces for human kind. We are surrounded by different In-betweennesses every day in indoor or outdoor spaces. Being aware of how to use this condition can make us better at forming stronger connections to nature, respecting the earth and following its movements, have more adaptability in our built environments, and having more transition, continuity and mobility in our spaces. This project is a work space building focused on health in architecture. considering biophilic design guidelines and active design guidelines I was focused on designing an adaptable workspace and finding design solutions for encouraging users to follow a healthier lifestyle, be more productive and motivated.

This dissertation is a study about belonging among the Fatanis who are caught between two places, namely Makkah and Jawi. Using historical and ethnographic data collected during two years of transnational fieldwork in Saudi Arabia, Thailand, and Malaysia, this dissertation shows that belonging is constituted as much by ideas of community, namely home and the homeland, as it is by lived experience as well as practical and cultural factors. Its central argument is that belonging is unstable, often incomplete, and always contingent owing to the dynamic quality of social life. Belonging is a condition that is volatile. It is not something that can be retained perpetually. A person might experience comfort from belonging someplace at a particular moment, while yearning to be somewhere else simultaneously. Thus, longing often accompanies belonging. In the late-eighteenth century, some Fatani men and women left Patani, on the northern Malay Peninsula, and sailed northwest until they arrived at Makkah. These migrants left in search of safety and inspiration as Siamese armies pillaged their homeland in attempts to depopulate Siam’s recalcitrant tributary kingdom from 1785-1839. Almost two and half centuries later, in contemporary times, the Fatanis are once again on the move. This time, unfavorable conditions in Makkah are the causes of reverse migration to the homeland, which the Fatanis refer to as Jawi. For the Fatanis, who are caught between Makkah and Jawi, belonging is elusive. Makkah, the place and society that many of them consider home, is familiar, but also where their right of residency as foreigners is fragile. On the other hand, Jawi, the homeland, is foreign to the Fatanis despite their status as nationals. From one page to another, this text tells the Fatanis’ stories of pain and yearning, but also of their ingenuity and perseverance. / Anthropology

The thesis focuses on the social web and on the analysis of social networks with particular emphasis on their temporal aspects. Social networks are represented here by Time Varying Graphs (TVG), a general model for dynamic graphs borrowed from distributed computing. In the first part of the thesis we focus on the temporal aspects of social networks. We develop various temporal centrality measures for TVGs including betweenness, closeness, and eigenvector centralities, which are well known in the context of static graphs. Unfortunately the computational complexities of these temporal centrality metrics are not comparable with their static counterparts. For example, the computation of betweenness becomes intractable in the dynamic setting. For this reason, approximation techniques will also be considered. We apply these temporal measures to two very different datasets, one in the context of knowledge mobilization in a small community of university researchers, the other in the context of Facebook commenting activities among a large number of web users. In both settings, we perform a temporal analysis so to understand the importance of the temporal factors in the dynamics of those networks and to detect nodes that act as “accelerators”. In the second part of the thesis, we focus on a more standard static graph representation. We conduct a propagation study on YouTube datasets to understand and compare the propagation dynamics of two different types of users: subscribers and friends. Finally, we conclude the thesis with the proposal of a general framework to present, in a comprehensive model, the influence of the social web on e-commerce decision making.

Ces dernières années, les réseaux sont devenus une source importante d’informations dans différents domaines aussi variés que les sciences sociales, la physique ou les mathématiques. De plus, la taille de ces réseaux n’a cessé de grandir de manière conséquente. Ce constat a vu émerger de nouveaux défis, comme le besoin de mesures précises et intuitives pour caractériser et analyser ces réseaux de grandes tailles en un temps raisonnable. La première partie de cette thèse introduit une nouvelle mesure de similarité entre deux noeuds d’un réseau dirigé et pondéré : la covariance “sum-over-paths”. Celle-ci a une interprétation claire et précise : en dénombrant tous les chemins possibles deux noeuds sont considérés comme fortement corrélés s’ils apparaissent souvent sur un même chemin – de préférence court. Cette mesure dépend d’une distribution de probabilités, définie sur l’ensemble infini dénombrable des chemins dans le graphe, obtenue en minimisant l'espérance du coût total entre toutes les paires de noeuds du graphe sachant que l'entropie relative totale injectée dans le réseau est fixée à priori. Le paramètre d’entropie permet de biaiser la distribution de probabilité sur un large spectre : allant de marches aléatoires naturelles où tous les chemins sont équiprobables à des marches biaisées en faveur des plus courts chemins. Cette mesure est alors appliquée à des problèmes de classification semi-supervisée sur des réseaux de taille moyennes et comparée à l’état de l’art. La seconde partie de la thèse introduit trois nouveaux algorithmes de classification de noeuds en sein d’un large réseau dont les noeuds sont partiellement étiquetés. Ces algorithmes ont un temps de calcul linéaire en le nombre de noeuds, de classes et d’itérations, et peuvent dés lors être appliqués sur de larges réseaux. Ceux-ci ont obtenus des résultats compétitifs en comparaison à l’état de l’art sur le large réseaux de citations de brevets américains et sur huit autres jeux de données. De plus, durant la thèse, nous avons collecté un nouveau jeu de données, déjà mentionné : le réseau de citations de brevets américains. Ce jeu de données est maintenant disponible pour la communauté pour la réalisation de tests comparatifs. La partie finale de cette thèse concerne la combinaison d’un graphe de citations avec les informations présentes sur ses noeuds. De manière empirique, nous avons montré que des données basées sur des citations fournissent de meilleurs résultats de classification que des données basées sur des contenus textuels. Toujours de manière empirique, nous avons également montré que combiner les différentes sources d’informations (contenu et citations) doit être considéré lors d’une tâche de classification de textes. Par exemple, lorsqu’il s’agit de catégoriser des articles de revues, s’aider d’un graphe de citations extrait au préalable peut améliorer considérablement les performances. Par contre, dans un autre contexte, quand il s’agit de directement classer les noeuds du réseau de citations, s’aider des informations présentes sur les noeuds n’améliora pas nécessairement les performances. La théorie, les algorithmes et les applications présentés dans cette thèse fournissent des perspectives intéressantes dans différents domaines. In recent years, networks have become a major data source in various fields ranging from social sciences to mathematical and physical sciences. Moreover, the size of available networks has grow substantially as well. This has brought with it a number of new challenges, like the need for precise and intuitive measures to characterize and analyze large scale networks in a reasonable time. The first part of this thesis introduces a novel measure between two nodes of a weighted directed graph: The sum-over-paths covariance. It has a clear and intuitive interpretation: two nodes are considered as highly correlated if they often co-occur on the same -- preferably short -- paths. This measure depends on a probability distribution over the (usually infinite) countable set of paths through the graph which is obtained by minimizing the total expected cost between all pairs of nodes while fixing the total relative entropy spread in the graph. The entropy parameter allows to bias the probability distribution over a wide spectrum: going from natural random walks (where all paths are equiprobable) to walks biased towards shortest-paths. This measure is then applied to semi-supervised classification problems on medium-size networks and compared to state-of-the-art techniques. The second part introduces three novel algorithms for within-network classification in large-scale networks, i.e., classification of nodes in partially labeled graphs. The algorithms have a linear computing time in the number of edges, classes and steps and hence can be applied to large scale networks. They obtained competitive results in comparison to state-of-the-art technics on the large scale U.S.~patents citation network and on eight other data sets. Furthermore, during the thesis, we collected a novel benchmark data set: the U.S.~patents citation network. This data set is now available to the community for benchmarks purposes. The final part of the thesis concerns the combination of a citation graph with information on its nodes. We show that citation-based data provide better results for classification than content-based data. We also show empirically that combining both sources of information (content-based and citation-based) should be considered when facing a text categorization problem. For instance, while classifying journal papers, considering to extract an external citation graph may considerably boost the performance. However, in another context, when we have to directly classify the network citation nodes, then the help of features on nodes will not improve the results. The theory, algorithms and applications presented in this thesis provide interesting perspectives in various fields.

The aim of this study has been to examine representations of Latino boys and young men in Latino American coming of age novels. Two concepts have been central to the study: positions of (in)betweenness and the ability to "fall in line" with norms and expectations. Three overarching themes are been explored in relation to masculinity. These are sexualities, ethnicities, and the representation of women. First, representations of queer sexualities are explored, focusing on the protagonists' "coming out" process and the varying reactions to this. The second part of this theme explores representations of disciplining strategies between boys and men as a means to regulating homosocial bonding and maintain the dominant masculinity ideal. The second theme, ethnicity, examines representations of "authentic" Latino identities in relation to language and bilingualism, and the link between location and identity. Disciplining measures aimed towards the protagonists, such as criminalization and dehumanization, are also explored. The final theme deals with the lacking representation of women in literature and research focused on men and masculinity. In the novels, women are depicted as confidants, present in the boys' lives mainly in order to provoke and facilitate their renegotiations of ideas regarding the previously discussed themes. The boys are represented as inhabiting positions of (in)betweenness throughout the novels, whether in relation to ethnicity, sexuality or gender. While (in)betweenness holds a potential to challenge and "worry" fixed categories, these positions are also characterized by unease, precariousness and the risk of being disciplined by other men.

An urban environment can be abstracted in form of a street network in order to be further analysed structurally. The urban street network can be represented in various ways by taking different principles and constraints into account. Therefore the aim of this work is to investigate human behaviour and communication in emerged urban phenomena, namely traffic flow and wayfinding, by structural characterization of an appropriate representation of an urban street network and modifying the conventional methods. / In order to characterize the depicted urban street network, centrality measure and specifically betweenness centrality is utilized. This analysis is then implemented to characterize the studied urban phenomena with respect to their structural, temporal and dynamic properties. In case of studying only the structural properties of the phenomena such as route description or self localization the conventional betweenness centrality is performed. But in case of studying the dynamic and temporal properties of a phenomenon such as traffic flow a modified version of betweenness centrality is proposed which considers dynamic and temporal aspects of human travel behaviour. / Experiments are designed to test the implementation of the suggested methods in the studied urban phenomena. The results of experiments demonstrate the efficiency of the proposed model in characterization of the studied urban phenomena in this thesis and then mention some of the problems and potential areas for future works.

Graph queries typically involve retrieving entities with certain properties and connectivity patterns. One popular property is betweenness centrality, which is a quantitative measure of importance used in many applications such as identifying influential users in social networks. Solving graph queries that involve retrieving important entities with user-defined connectivity patterns in large graphs requires efficient com- putation of betweenness centrality and efficient graph query engines. The first part of this thesis studies the betweenness centrality problem, while the second part presents a framework for building efficient graph query engines. Computing betweenness centrality entails computing all-pairs shortest paths; thus, exact computation is costly. The performance of existing approximation algorithms is not well understood due to the lack of an established benchmark. Since graphs in many applications are inherently evolving, several incremental algorithms were proposed. However, they cannot scale to large graphs: they either require excessive memory or perform unnecessary computations rendering them prohibitively slow. Existing graph query engines rely on exhaustive indices for accelerating query evaluation. The time and memory required to build these indices can be prohibitively high for large graphs. This thesis attempts to solve the aforementioned limitations in the graph analytics literature as follows. First, we present a benchmark for evaluating betweenness centrality approximation algorithms. Our benchmark includes ground-truth data for large graphs in addition to a systematic evaluation methodology. This benchmark is the first attempt to standardize evaluating betweenness centrality approximation algorithms and it is currently being used by several research groups working on approximate between- ness in large graphs. Then, we present a linear-space parallel incremental algorithm for updating betweenness centrality in large evolving graphs. Our algorithm uses biconnected components decomposition to localize processing graph updates, and it performs incremental computation even within affected components. Our algorithm is up to an order of magnitude faster than the state-of-the-art parallel incremental algorithm. Finally, we present a framework for building low memory footprint graph query engines. Our framework avoids building exhaustive indices and uses highly optimized matrix algebra operations instead. Our framework loads datasets, and evaluates data-intensive queries up to an order of magnitude faster than existing engines.

No description available.

It is currently understood that diseases are typically not caused by rogue errors in genetics but have both molecular and environmental causes from myriad overlapping interactions within an interactome. Genetic errors, such as that seen by a single-nucleotide polymorphism can lead to a dysfunctional cell, which in turn can lead to systemic disruptions that result in disease phenotypes. Perturbations within the interactome, as can be caused by many such errors, can be organized into a pathophenotype, or “disease module”. Disease modules are sets of correlated variables that can represent many of a disease’s activities with subgraphs of nodes and edges. Many methods for inferring disease modules are available today, but the results each one yields is not only variable between methods but also across datasets and trial attempts. In this study, several such inference methods for deriving disease modules are evaluated by combining them to create “consensus” modules. The method of focus is Double-Specific Betweenness (S2B), which uses betweenness centrality across separate diseases to derive new modules. This study, however, uses S2B to combine the results of independent inference methods rather than separate diseases to derive new modules. Pre-processed asthma and arthritis data are compared using various combinations of inference methods. The performance of each result is validated using Pathway Scoring Algorithm. The results of this study suggest that combining methods of inference using MODifieR or S2B may be beneficial for deriving meaningful disease modules.