Dissertations / Theses on the topic 'Preferential attachment'

Preferential attachment networks with power law degree sequence undergo a phase transition when the power law exponent τ changes. For τ > 3 typical distances in the network are logarithmic in the size of the network and for 2 < τ < 3 they are doubly logarithmic. In this thesis, we identify the correct scaling constant for τ ∈ (2, 3) and discover a surprising dichotomy between preferential attachment networks and networks without preferential attachment. This contradicts previous conjectures of universality. Moreover, using a model recently introduced by Dereich and Mörters, we study the critical behaviour at τ = 3, and establish novel results for the scale of the typical distances under lower order perturbations of the attachment function.

L’inégalité est une caractéristique notoire des systèmes sociaux. Dans cette thèse, nous nous attarderons à la distribution et à la structure de la répartition de leurs ressources et activités. Dans ce contexte, leurs extrêmes iniquités tendent à suivre une propriété universelle, l’indépendance d’échelle, qui se manifeste par l’absence d’échelle caractéristique. En physique, les organisations indépendantes d’échelle sont bien connues en théorie des transitions de phase dans laquelle on les observe à des points critiques précis. Ceci suggère que des mécanismes bien définis sont potentiellement responsables de l’indépendance d’échelle des systèmes sociaux. Cette analogie est donc au coeur de cette thèse, dont le but est d’aborder ce problème de nature multidisciplinaire avec les outils de la physique statistique. En premier lieu, nous montrons qu’un système dont la distribution de ressource croît vers l’indépendance d’échelle se trouve assujetti à deux contraintes temporelles particulières. La première est l’attachement préférentiel, impliquant que les riches s’enrichissent. La seconde est une forme générale de comportement d’échelle à délai entre la croissance de la population et celle de la ressource. Ces contraintes dictent un comportement si précis qu’une description instantanée d’une distribution est suffisante pour reconstruire son évolution temporelle et prédire ses états futurs. Nous validons notre approche au moyen de diverses sphères d’activités humaines dont les activités des utilisateurs d’une page web, des relations sexuelles dans une agence d’escorte, ainsi que la productivité d’artistes et de scientifiques. En second lieu, nous élargissons notre théorie pour considérer la structure résultante de ces activités. Nous appliquons ainsi nos travaux à la théorie des réseaux complexes pour décrire la structure des connexions propre aux systèmes sociaux. Nous proposons qu’une importante classe de systèmes complexes peut être modélisée par une construction hiérarchique de niveaux d’organisation suivant notre théorie d’attachement préférentiel. Nous montrons comment les réseaux complexes peuvent être interprétés comme une projection de ce modèle de laquelle émerge naturellement non seulement leur indépendance d’échelle, mais aussi leur modularité, leur structure hiérarchique, leurs caractéristiques fractales et leur navigabilité. Nos résultats suggèrent que les réseaux sociaux peuvent être relativement simples, et que leur complexité apparente est largement une réflexion de la structure hiérarchique complexe de notre monde.
Social systems are notoriously unfair. In this thesis, we focus on the distribution and structure of shared resources and activities. Through this lens, their extreme inequalities tend to roughly follow a universal pattern known as scale independence which manifests itself through the absence of a characteristic scale. In physical systems, scale-independent organizations are known to occur at critical points in phase transition theory. The position of this critical behaviour being very specific, it is reasonable to expect that the distribution of a social resource might also imply specific mechanisms. This analogy is the basis of this work, whose goal is to apply tools of statistical physics to varied social activities. As a first step, we show that a system whose resource distribution is growing towards scale independence is subject to two constraints. The first is the well-known preferential attachment principle, a mathematical principle roughly stating that the rich get richer. The second is a new general form of delayed temporal scaling between the population size and the amount of available resource. These constraints pave a precise evolution path, such that even an instantaneous snapshot of a distribution is enough to reconstruct its temporal evolution and predict its future states. We validate our approach on diverse spheres of human activities ranging from scientific and artistic productivity, to sexual relations and online traffic. We then broaden our framework to not only focus on resource distribution, but to also consider the resulting structure. We thus apply our framework to the theory of complex networks which describes the connectivity structure of social, technological or biological systems. In so doing, we propose that an important class of complex systems can be modelled as a construction of potentially infinitely many levels of organization all following the same universal growth principle known as preferential attachment. We show how real complex networks can be interpreted as a projection of our model, from which naturally emerge not only their scale independence, but also their clustering or modularity, their hierarchy, their fractality and their navigability. Our results suggest that social networks can be quite simple, and that the apparent complexity of their structure is largely a reflection of the complex hierarchical nature of our world.

In this paper we introduce the concept of preferential attachment in the context of recommendation and rating systems. We present several models incorporating different qualities that may manifest in such systems, such as inherent bias, and examine the resulting degree distributions (i.e. ratings) as snapshots and through time. We then take preliminary steps towards testing real-world feasibility with the Yelp Academic Dataset.

Complex networks are composed of a large number of interacting nodes. Examples of complex networks include the topology of the Internet, connections between websites or web pages in the World Wide Web (WWW), and connections between participants in social networks.Due to their ubiquity, modeling complex networks is importantfor answering many research questions that cannot be answered without a mathematical model. For example, mathematical models of complex networks can be used to find the most vulnerable nodes to protect during a virus attack in theInternet, to predict connections between websites in the WWW, or to find members of different communities insocial networks. Researchers have analyzed complex networksand concluded that they are distinguished from other networks by four specific statistical properties. These four statistical properties are commonly known in this field as: (i) thesmall world effect,(ii) high average clustering coefficient, (iii) scale-free power law degree distribution, and (iv) emergence of community structure. These four statistical properties are further described later in this dissertation. Mostmodels used to generate complex networks attempt to produce networks with these statistical properties. Additionally, most of these network models generate homogeneous complex networks where all the networknodes are considered to have the same properties. Homogenous complex networks neglect the heterogeneous nature ofthe nodes in many complexnetworks. Moreover, somemodels proposed for generating heterogeneous complexnetworks are not general as they make specific assumptions about the properties of the network.Including heterogeneity in the connection algorithm of a modelwould makeitmore suitable for generating the subset of complex networks that exhibit selective linking.Additionally, all modelsproposed, to date, for generating heterogeneous complex networks do not preserve all four of the statistical properties of complexnetworks stated above. Thus, formulation of a model for the generation of general heterogeneous complex networkswith characteristics that resemble as much as possible the statistical properties common to the real-world networks that have received attention from the research community is still an open research question. In this work, we propose two new types of models to generate heterogeneous complex networks. First, we introduce the Integrated Attribute Similarity Model (IASM). IASM uses preferential attachment(PA) to connect nodes based on a similarity measure for node attributes combined with a node's structural popularity measure. IASM integrates the attribute similarity measure and a structural popularity measure in the computation of the connection function used to determine connectionsbetween each arriving (newly created) node and the existing(previously created or old) network nodes. IASM is also the first model known to assign an attribute vector having more than one element to each node, thus allowing different attributes per node in the generated complex network. Networks generated using IASM have a power law degree distribution and preserve the small world phenomenon. IASM models are enhanced to increase their clustering coefficient using a triad formation step (TFS). In a TFS, a node connects to the neighbor of the node to which it was previously connected through preferential attachment, thus forming a triad. The TFS increases the number of triads that are formed in the generated network which increases the network's average clustering coefficient. We also introduce a second novel model,the Settling Node Adaptive Model (SNAM). SNAM reflects the heterogeneous nature of connectionstandard requirements for nodes. The connectionstandard requirements for a noderefers to the values of attribute similarity and/or structural popularityof old node ythat node new xwould find acceptable in order to connect to node y.SNAM is novel in that such a node connection criterion is not included in any previous model for the generation of complex networks. SNAM is shown to be successful in preserving the power law degree distribution, the small world phenomenon, and the high clustering coefficient of complex networks. Next,we implement a modification to the IASM and SNAM models that results in the emergence of community structure.Nodes are classified into classes according to their attribute values. The connection algorithm is modified to include the class similarity values between network nodes. This community structure model preservesthe PL degree distribution, small world property, and does not affect average clustering coefficient values expected from both IASM and SNAM. Additionally, the model exhibits the presence of community structure having most of the connections made between nodes belonging to the same class with only a small percent of the connections made between nodes of different classes. We perform a mathematical analysis of IASM and SNAM to study the degree distribution for networks generated by both models. This mathematical analysis shows that networks generated by both models have a power law degree distribution. Finally, we completed a case study to illustrate the potential value of our research on the modeling of heterogeneous complex networks. This case study was performed on a Facebook dataset. The case study shows that SNAM, with some modifications to the connection algorithm, is capable of generating a network with almost the same characteristics as found for the original dataset. The case study providesinsight on how the flexibility of SNAM's connection algorithm can be an advantagethat makes SNAM capable of generating networks with different statistical properties. Ideas for future research areas includestudyingthe effect of using eigenvector centrality, instead of degree centrality, on the emergence of community structure in IASM; usingthe nodeindex as an indication for its order of arrival to the network and distributing added connections fairly among networknodes along the life of the generated network; experimenting with the nature of attributesto generatea more comprehensive model; and usingtime sensitive attributes in the models, where the attribute can change its value with time,
Ph. D.

Um dos objetivos das próximas gerações dos sistemas de comunicação é permitir que os usuários acessem e distribuam um ou mais serviços a qualquer hora, em qualquer lugar, independentemente do tipo de terminal (telefone convencional, telefone celular, assistentes pessoais digitais, notebooks, dentre outros) ou da tecnologia da rede de acesso utilizados. Esse cenário é denominado convergência de serviços utilizando-se redes heterogêneas, e em tal realidade, as arquiteturas de qualidade de serviço existentes em cada uma das tecnologias dos sistemas de comunicação não oferecem mecanismos de interoperabilidade e em diversos casos não há controle sob os fluxos de dados uma vez admitido na infraestrutura do sistema de comunicação, assim como questões de handover heterogêneo não são tratadas. A tese propõe uma arquitetura para controle de Qualidade de Serviço para um ambiente heterogêneo composto de backbones IP e redes de acesso de diversas tecnologias, sendo tal arquitetura composta de agentes autônomos e distribuídos nos equipamentos de um sistema de comunicação; assim como.controles baseados no comportamento de uma região de um sistema de comunicação e apoiados na teoria e princípios de sistemas complexos. Os agentes da arquitetura proposta utilizando o princípio de preferential attachment mostraram-se eficientes na determinação do caminho de melhor condição de qualidade de serviços. Os componentes da arquitetura proposta estão localizados em cada equipamento de comunicação, desde o dispositivo do usuário até o provedor de serviços. As medições realizadas pelos agentes e utilizando um algoritmo baseado no conceito de preferential attachment permitiram ao agente alterar o caminho de um fluxo de dados durante sua transmissão para outros caminhos que apresentaram condições mais adequadas de acordo com os parâmetros de QoS. A decisão é baseada no contrato de qualidade de serviço especificado entre usuário e provedor de serviço e, considerando sob controle todos os elementos envolvidos na comunicação; tem-se controle distribuído de qualidade de serviço fim a fim.
One of the targets of the next generation communication systems is to provide access to any service, to any user, anytime, anywhere, regardless the access network technology or type of user device (mobile phone, PDA, personal computer, and so on). This scenario is called convergence of services by heterogeneous networks, and in such scenario quality of service mechanisms presented in legacy communication systems do not provide mechanisms for interoperability between communication systems nor control data flows after control admission in the border of the communication systems. The heterogeneous handover is also not handled by such QoS architectures. This thesis proposes a QoS control architecture for an heterogeneous communication systems composed by IP backbones and several access networks for several kind of technologies. This architecture is composed by a multiagent system and has controls based on the local behavior of the communication system and supported by complex systems theory. The agent decision algorithm is based on preferential attachment concept and the experimentation results indicate that agents could identify a better path to handle a data flow according to QoS parameters. The agents decided to change the path used to transmit the flow data autonomously and according to quality of service contract between user and service provider. The measurements in the test based on preferential attachment algorithm was useful in order agent change flow data path during data flow transmission to other paths with better conditions according to QoS requisites. The agent decision is based on the parameter values defined between end user and service provider. Considering the control elements from proposed architecture it was achieved end-to-end distributed control.

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.

Computer and Information Science
Ph.D.
Rather than being randomly wired together, the components of complex network systems are recently reported to represent a scale-free architecture, in which the node degree distribution follows power-law. While social networks are scale-free, it is natural to utilize their structural properties in some social network applications. As a result, this dissertation explores social network architectures, and in turn, leverages these architectures to facilitate some influence and information propagation applications. Social network architectures are analyzed in two different aspects. The first aspect focuses on the node degree snowballing effects (i.e., degree growth effects) in social networks, which is based on an age-sensitive preferential attachment model. The impact of the initial links is explored, in terms of accelerating the node degree snowballing effects. The second aspect focuses on Nested Scale-Free Architectures (NSFAs) for social networks. The scale-free architecture is a classic concept, which means that the node degree distribution follows the power-law distribution. `Nested' indicates that the scale-free architecture is preserved when low-degree nodes and their associated connections are iteratively removed. NSFA has a bounded hierarchy. Based on the social network structure, this dissertation explores two influence propagation applications for the Social Influence Maximization Problem (SIMP). The first application is a friend recommendation strategy with the perspective of social influence maximization. For the system provider, the objective is to recommend a fixed number of new friends to a given user, such that the given user can maximize his/her social influence through making new friends. This problem is proved to be NP-hard by reduction from the SIMP. A greedy friend recommendation algorithm with an approximation ratio of $1-e^{-1}$ is proposed. The second application studies the SIMP with the crowd influence, which is NP-hard, monotone, non-submodular, and inapproximable in general graphs. However, since user connections in Online Social Networks (OSNs) are not random, approximations can be obtained by leveraging the structural properties of OSNs. The modularity, denoted by $\Delta$, is proposed to measure to what degree this problem violates the submodularity. Two approximation algorithms are proposed with ratios of $\frac{1}{\Delta+2}$ and $1-e^{-1/(\Delta+1)}$, respectively. Beside the influence propagation applications, this dissertation further explores three different information propagation applications. The first application is a social network quarantine strategy, which can eliminate epidemic outbreaks with minimal isolation costs. This problem is NP-hard. An approximation algorithm with a ratio of 2 is proposed through utilizing the problem properties of feasibility and minimality. The second application is a rating prediction scheme, called DynFluid, based on the fluid dynamics. DynFluid analogizes the rating reference among the users in OSNs to the fluid flow among containers. The third application is an information cascade prediction framework: given the social current cascade and social topology, the number of propagated users at a future time slot is predicted. To reduce prediction time complexities, the spatiotemporal cascade information (a larger size of data) is decomposed to user characteristics (a smaller size of data) for subsequent predictions. All these three applications are based on the social network structure.
Temple University--Theses

Real-world large-scale complex networks such as the Internet, social networks and biological networks have increasingly attracted the interest of researchers from many areas. Accurate modelling of the statistical regularities of these large-scale networks is critical to understand their global evolving structures and local dynamical patterns. Traditionally, the Erdos and Renyi random graph model has helped the investigation of various homogeneous networks. During the past decade, a special computational methodology has emerged to study complex networks, the outcome of which is identified by two models: the Watts and Strogatz small-world model and the Barabasi-Albert scale-free model. At the core of the complex network modelling process is the extraction of characteristics of real-world networks. I have developed computer simulation algorithms for study of the properties of current theoretical models as well as for the measurement of two real-world complex networks, which lead to the isolation of three complex network modelling essentials. The main contribution of the thesis is the introduction and study of a new General Two-Stage growth model (GTS Model), which aims to describe and analyze many common-featured real-world complex networks. The tools we use to create the model and later perform many measurements on it consist of computer simulations, numerical analysis and mathematical derivations. In particular, two major cases of this GTS model have been studied. One is named the U-P model, which employs a new functional form of the network growth rule: a linear combination of preferential attachment and uniform attachment. The degree distribution of the model is first studied by computer simulation, while the exact solution is also obtained analytically. Two other important properties of complex networks: the characteristic path length and the clustering coefficient are also extensively investigated, obtaining either analytically derived solutions or numerical results by computer simulations. Furthermore, I demonstrate that the hub-hub interaction behaves in effect as the link between a network's topology and resilience property. The other is called the Hybrid model, which incorporates two stages of growth and studies the transition behaviour between the Erdos and Renyi random graph model and the Barabasi-Albert scale-free model. The Hybrid model is measured by extensive numerical simulations focusing on its degree distribution, characteristic path length and clustering coefficient. Although either of the two cases serves as a new approach to modelling real-world large-scale complex networks, perhaps more importantly, the general two-stage model provides a new theoretical framework for complex network modelling, which can be extended in many ways besides the two studied in this thesis.

Entendimento de processos que levem ao surgimento de opiniões extremas é valioso na prevenção de atos de violência. Os modelos são ferramentas úteis para identificar possíveis padrões relacionados a estes processos. No entanto, modelos discretos ou contínuos com confiança limitada não se mostram adequados para estudar dinâmicas caracterizadas pela divergência de opiniões. É proposta uma extensão cultural do modelo de Opiniões Contínuas e Ações Discretas (CODA) com múltiplos assuntos alternados por um mecanismo de ligação preferencial. Os agentes são influenciados não só em suas opiniões, mas também nas importâncias que atribuem aos diferentes assuntos. As principais características do modelo são o surgimento de preferências e consensos locais, aos quais estão associadas as opiniões mais extremas. Há, em contrapartida, persistência de opiniões brandas nos temas menos preferidos. O estudo do espaço paramétrico do modelo revelou que modificações diminuindo a localidade das interações aumentam maiorias e amenizam opiniões. Duas estratégias distintas de debate foram testadas. Zelotes têm poder de conversão aumentado quando dispersos. Evitadores minimizam o número de interações indesejável se agrupados. Foram esboçadas abordagens para inserção de efeitos da mídia na dinâmica
Understanding processes leading to extremism is invaluable to prevent violence outbursts. Models are useful tools that allow for identifying patterns related to those processes. Nevertheless, discrete models and bounded-confidence continuous models are unfit for studying diversion-based dynamics. We present a cultural extension of CODA model, with multiple subjects selected through a preferential attachment rule. Agents are influenced in their opinions and relevance attributed to different subjects. The most notable results of the dynamics are the establishment of local subject preferences and consensus, associated with more extreme opinions. On the other hand, there is persistence of immature undeveloped opinion in the locally less regarded subjects. The study of parametric space has shown that settings reducing the locality of interactions both increase the majority size and make opinions less extreme. Two distinct debate strategies were simulated. Zealots increase conversions when spread throughout the network. In contrast, subject avoiders decrease the number of unwanted interactions by grouping together. Some ideas for introducing media influence to the model were outlined

Empirical studies show that similar patterns emerge from a large number of different biological systems. For example, the group size distributions of several fish species and house sparrows all follow power law distributions with an exponential truncation. Networks built by ant colonies, slime mold and those are designed by engineers resemble each other in terms of structure and transportation efficiency. Based on the investigation of experimental data, we propose a variety of simple stochastic models to unravel the underlying mechanisms which lead to the collective phenomena in different systems. All the mechanisms employed in these models are rooted in the concept of selective reinforcement. In some systems the reinforcement can build optimal solutions for biological problem solving. This thesis consists of five papers. In the first three papers, I collaborate with biologists to look into group formation in house sparrows  and the movement decisions of damsel fish.  In the last two articles, I look at how shortest paths and networks are  constructed by slime molds and pheromone laying ants, as well as studying  speed-accuracy tradeoffs in slime molds' decision making. The general goal of the study is to better understand how macro level patterns and behaviors emerges from micro level interactions in both spatial and non-spatial biological systems. With the combination of mathematical modeling and experimentation, we are able to reproduce the macro level patterns in the studied biological systems and predict behaviors of the systems using minimum number of parameters.

We consider a general preferential attachment model, where the probability that a newly arriving vertex connects to an older vertex is proportional to a (sub-)linear function of the indegree of the older vertex at that time. We provide a limit theorem with rates of convergence for the distribution of a vertex, chosen uniformly at random, as the number of vertices tends to infinity. To do so, we develop Stein's method for a new class of limting distributions including power-laws. Similar, but slightly weaker results are shown to be deducible using coupling techniques. Concentrating on a specific preferential attachment model we also show that the outdegree distribution asymptotically follows a Poisson law. In addition, we deduce a central limit theorem for the number of isolated vertices. We thereto construct a size-bias coupling which in combination with Stein’s method also yields bounds on the distributional distance.

碩士
輔仁大學
資訊管理學系碩士班
107
Nowdays, the social media and internet users are universal, users’ choice of social media is increasing, but users have different needs for choosing social media, in addition, does the users sharing of knowledge on social media have an impact on their personal needs? However, this study explore the perspectives of preferential attachment, self-referential value, group reference value and entertainment reference value, trying to explore the impact of preferential attachment , self-referential value, group reference value and entertainment reference on social media, three values have an impact on the choice and use of social media, and understand the users knowledge sharing intentions. 　　This study sets the research community to the professional community members in the social media, and conduct an online survey by electronic questionnaire, this study assumes that the three facets of self-reference value, group reference value and entertainment reference will affect users choice of community media, community belonging and knowledge sharing intention; It is also assumed that the continued use of social media by users will affect the users sense of belonging to the community and the intention to share knowledge because of the preferential attachment. Measuring user preferential attachment, knowledge sharing intentions as a way to measure the impact of social media usage, after, this study will use the statistical analysis software to confirm the consistency, stability and reliability of the test results the reliability and validity of the questionnaire, in addition, this study also through Independent-Sample T test test this study whether have nonresponse error, to confirm the findings of this study. In the end, hypothetical inferences are analyzed through structural equation model to understand their statistical inferences. 　　After collecting 155 usable responses, this study finding self-reference value, group reference value and entertainment reference had positive correlation with social belonging, the self-reference value, group reference value and entertainment reference had positive correlation with preferential attachment, the self-reference value, group reference value and entertainment reference had positive correlation with knowledge sharing intentions, the preferential attachment had positive correlation with knowledge sharing intentions, but preferential attachment had not positive correlation with social belonging, the entertainment reference had not positive correlation with preferential attachment, the social belonging had not positive correlation with knowledge sharing intentions. Finally in the practical meaning, we conclude about theortical and managerial implications propose discussion and conclusion.

Networks arise in nearly every branch of science, from biology and physics to sociology and economics. A signature of many network datasets is strong local dependence, which gives rise to phenomena such as sparsity, power law degree distributions, clustering, and structural heterogeneity. Statistical models of networks require a careful balance of flexibility to faithfully capture that dependence, and simplicity, to make analysis and inference tractable. In this dissertation, we introduce a class of models that insert one network edge at a time via a random walk, permitting the location of new edges to depend explicitly on the structure of the existing network, while remaining probabilistically and computationally tractable. Connections to graph kernels are made through the probability generating function of the random walk length distribution. The limiting degree distribution is shown to exhibit power law behavior, and the properties of the limiting degree sequence are studied analytically with martingale methods. In the second part of the dissertation, we develop a class of particle Markov chain Monte Carlo algorithms to perform inference for a large class of sequential random graph models, even when the observation consists only of a single graph. Using these methods, we derive a particle Gibbs sampler for random walk models. Fit to synthetic data, the sampler accurately recovers the model parameters; fit to real data, the model offers insight into the typical length scale of dependence in the network, and provides a new measure of vertex centrality. The arrival times of new vertices are the key to obtaining results for both theory and inference. In the third part, we undertake a careful study of the relationship between the arrival times, sparsity, and heavy tailed degree distributions in preferential attachment-type models of partitions and graphs. A number of constructive representations of the limiting degrees are obtained, and connections are made to exchangeable Gibbs partitions as well as to recent results on the limiting degrees of preferential attachment graphs.

This thesis covers four topics: i) Measuring dependence in time series through distance covariance; ii) Testing goodness-of-fit of time series models; iii) Threshold selection for multivariate heavy-tailed data; and iv) Inference for linear preferential attachment networks. Topic i) studies a dependence measure based on characteristic functions, called distance covariance, in time series settings. Distance covariance recently gathered popularity for its ability to detect nonlinear dependence. In particular, we characterize a general family of such dependence measures and use them to measure lagged serial and cross dependence in stationary time series. Assuming strong mixing, we establish the relevant asymptotic theory for the sample auto- and cross- distance correlation functions. Topic ii) proposes a goodness-of-fit test for general classes of time series model by applying the auto-distance covariance function (ADCV) to the fitted residuals. Under the correct model assumption, the limit distribution for the ADCV of the residuals differs from that of an i.i.d. sequence by a correction term. This adjustment has essentially the same form regardless of the model specification. Topic iii) considers data in the multivariate regular varying setting where the radial part $R$ is asymptotically independent of the angular part $\Theta$ as $R$ goes to infinity. The goal is to estimate the limiting distribution of $\Theta$ given $R\to\infty$, which characterizes the tail dependence of the data. A typical strategy is to look at the angular components of the data for which the radial parts exceed some threshold. We propose an algorithm to select the threshold based on distance covariance statistics and a subsampling scheme. Topic iv) investigates inference questions related to the linear preferential attachment model for network data. Preferential attachment is an appealing mechanism based on the intuition “the rich get richer” and produces the well-observed power-law behavior in net- works. We provide methods for fitting such a model under two data scenarios, when the network formation is given, and when only a single-time snapshot of the network is observed.

碩士
東海大學
景觀學系
99
There is a variety of plants in Taiwan bonsai. As a bonsai is a miniature of natural landscape, many people like to use it for gardening or indoor decoration. The bonsai is one part of plant growing, and the plant growing is an essential element in landscape. Over the past few years on discussing the landscape, most of the researches focused on the aesthetics and the space layout of plant growing, and most of the probes were made based on the linear and plane dimensions. As to the research on single element “bonsai”, the research cases were very few, and could be counted on the fingers of one hand. Taiwan bonsai has its unique characters. This essay will probe into the unique characters and the cultural values of the representative and valuable bonsai of Taiwan through the experts and the literature reviews. This essay is expected to be informative to the Taiwan bonsai creators. As to the general public, this essay is expected to be able to help them to discover the cultural values and the charm behind the bonsai when they make selections on bonsai.

This thesis concerns chosen problems of privacy preserving data aggregation. It is based on differential privacy, which is a mathematically rigorous privacy definition resilient to post-processing. Differential privacy is connected with randomization of the result. The goal is to achieve both sufficient privacy and accuracy. We are interested in practical scenarios, so we consider aggregation in distributed systems with unreliable nodes and untrusted aggregator. First, we analyse current state-of-the-art solution and show that despite good asymptotical guarantees for the accuracy, in many practical scenarios the errors are unacceptably high. We present our own fault tolerant privacy preserving data aggregation protocol which utilizes limited local communication between nodes. We show that our protocol provides provable level of privacy and far better accuracy even when facing massive failures of nodes. Next, to make our results useful in wider scenarios, we show how to construct local groups of trust in real-life networks. We consider a distributed system that consists of nodes which need to constitute a huge, connected group in an efficient way, using simple operations and without knowledge of global network topology. We propose and investigate local strategies for constructing large groups of users with low communication and computation overhead. Moreover, we prove some properties of real-life networks while formally assuming that they are generated as a preferential attachment process. Finally, we took a different approach and focused instead on the privacy definition itself. We look from different perspective at an, already known, relaxation of differential privacy called noiseless privacy. It utilizes the randomness in the data, which can either come inherently from the data itself, or model the uncertainty of the Adversary. In contrast to previous work, which focused on asymptotic results, independent data and specific distributions, we give nonasymptotic privacy guarantees for any distribution and a wide class of dependencies. We show a way to combine differential privacy with noiseless privacy and present detailed results which can be easily applied in real-life scenarios of data aggregation.
Przedmiotem tej rozprawy s ˛a wybrane problemy agregacji danych z zachowaniem prywatnosci. Rozprawa jest oparta o ´ prywatnos´c ró ´ znicow ˛a ˙ (differential privacy), która, w odróznieniu od wcze ˙ sniejszych definicji prywatno ´ sci, jest oparta na for- ´ malizmie matematycznym. Prywatnos´c ró ´ znicowa wi ˛a ˙ ze si˛e z odpowiedni ˛a ran- ˙ domizacj ˛a wyniku. Interesuj ˛a nas praktyczne scenariusze, wi˛ec rozwazamy agre- ˙ gacje w rozproszonych systemach z zawodnymi w˛ezłami i niezaufanym agregatorem. Zaczniemy od przeanalizowania aktualnego rozwi ˛azania problemu i wskazania, ze pomimo dobrych asymptotycznych gwarancji dokładno ˙ sci, w wielu prakty- ´ cznych scenariuszach bł˛edy wynikaj ˛ace z dodanych szumów s ˛a nieakceptowalnie duze. Nast˛epnie proponujemy skonstruowany przez nas protokół, który wyko- ˙ rzystuje ograniczon ˛a, lokaln ˛a komunikacj˛e pomi˛edzy w˛ezłami. Pokazujemy, ze˙ nasz protokół zapewnia dowodliw ˛a prywatnos´c oraz jest znacznie dokładniejszy, ´ nawet gdy wiele w˛ezłów jest zawodnych. Nast˛epnie, aby nasze wyniki były uzyteczne w szerszej klasie scenariuszy, pokazu- ˙ jemy jak skonstruowac lokalne grupy ufaj ˛acych sobie w˛ezłów w realistycznych ´ sieciach. Rozwazamy rozproszony system składaj ˛acy si˛e z w˛ezłów, które musz ˛a ˙ stworzyc du ´ z ˛a, spójn ˛a grup˛e w sposób efektywny i bez znajomo ˙ sci topologii sieci. ´ Proponujemy i badamy lokalne strategie konstruowania duzych grup z małym ˙ narzutem komunikacyjnym i obliczeniowym. Ponadto udowadniamy niektóre własnosci prawdziwych sieci przy zało ´ zeniu, ˙ ze pochodz ˛a z modelu ˙ preferential attachment. Na koniec koncentrujemy si˛e na samej definicji prywatnosci. Rozwa ´ zamy, znane ˙ wczesniej, osłabienie prywatno ´ sci ró ´ znicowej, ˙ noiseless privacy, wykorzystuj ˛ace ograniczon ˛a losowos´c danych. Mo ´ ze ona równie ˙ z modelowa ˙ c niepewno ´ s´c adw- ´ ersarza. W odróznieniu od istniej ˛acych wyników, które skupiały si˛e na wynikach ˙ asymptotycznych, niezaleznych danych i konkretnych rozkładach danych, przed- ˙ stawiamy nieasymptotyczne gwarancje prywatnosci dla dowolnych rozkładów i ´ szerokiej klasy zalezno ˙ sci. Pokazujemy jak poł ˛aczy ´ c prywatno ´ s´c ró ´ znicow ˛a z ˙ noiseless privacy oraz przedstawiamy precyzyjne wyniki, które mog ˛a byc łatwo ´ wykorzystane w praktycznych zastosowaniach agregacji danych.