Small World Folksonomies: Clustering in Tri-Partite Hypergraphs

Many recent Web 2.0 resource sharing applications can be subsumed under the "folksonomy" moniker. Regardless of the type of resource shared, all of these share a common structure describing the assignment of tags to resources by users. In this report, we generalize the notions of clustering and characteristic path length which play a major role in the current research on networks, where they are used to describe the small-world effects on many observable network datasets. To that end, we show that the notion of clustering has two facets which are not equivalent in the generalized setting. The new measures are evaluated on two large-scale folksonomy datasets from resource sharing systems on the web.

Network properties of folksonomies

Social resource sharing systems like YouTube and del.icio.us have acquired a large number of users within the last few years. They provide rich resources for data analysis, information retrieval, and knowledge discovery applications. A first step towards this end is to gain better insights into content and structure of these systems. In this paper, we will analyse the main network characteristics of two of the systems. We consider their underlying data structures – socalled folksonomies – as tri-partite hypergraphs, and adapt classical network measures like characteristic path length and clustering coefficient to them. Subsequently, we introduce a network of tag co-occurrence and investigate some of its statistical properties, focusing on correlations in node connectivity and pointing out features that reflect emergent semantics within the folksonomy. We show that simple statistical indicators unambiguously spot non-social behavior such as spam.

Network properties of folksonomies

Social resource sharing systems like YouTube and del.icio.us have acquired a large number of users within the last few years. They provide rich resources for data analysis, information retrieval, and knowledge discovery applications. A first step towards this end is to gain better insights into content and structure of these systems. In this paper, we will analyse the main network characteristics of two of these systems. We consider their underlying data structures – so-called folksonomies – as tri-partite hypergraphs, and adapt classical network measures like characteristic path length and clustering coefficient to them. Subsequently, we introduce a network of tag cooccurrence and investigate some of its statistical properties, focusing on correlations in node connectivity and pointing out features that reflect emergent semantics within the folksonomy. We show that simple statistical indicators unambiguously spot non-social behavior such as spam.

Interferometrische Sensoren mit Modulation der optischen Weglänge für die Fertigungsmesstechnik

Ziel dieser Dissertation ist es, eine Klasse interferometrischer Messgeräte zu charakterisieren und weiter zu entwickeln. Die Modulation der optischen Weglänge (OPLM) im Referenzarm eines interferometrischen Messsystems ist ein anpassungsfähiger Ansatz. Sie ist zur Messung von Oberflächenprofilen mit einer Auflösung bis in den sub-nm-Bereich bei einem Messbereich von bis zu 100 Mikrometer geeignet. Wird ein statisches Messobjekt gemessen, tritt durch die Modulation im Referenzarm am Detektor ein periodisches Interferenzmuster auf. Dies ist in der unten stehenden Abbildung schematisch dargestellt. Bei einer Veränderung des Abstandes zwischen Objekt und Messgerät kann aus der Phasen- und/oder Hüllkurvenverschiebung im Interferenzmuster die Abstandsänderung abgeleitet werden.Im Rahmen der Arbeit sind zwei funktionsfähige OPLM-Messsysteme entwickelt, aufgebaut und getestet worden. Diese demonstrieren, dass der OPLM-Ansatz ein breites Spektrum an Anwendungen durch eine optische Messung abdecken kann. Allerdings zeigen sich an den Messsystemen auch die Limitierungen des OPLM-Ansatzes. Die Systeme basieren auf einer Punktmessung mittels einer fasergekoppelten Sonde sowie auf einer linienförmigen Messung durch eine Zeilenkamera. Um eine hohe laterale Auflösung zu erzielen, wird die Zeilenkamera mit einem Mikroskop kombiniert. Damit flächenhaft gemessen werden kann, ist es notwendig, Messobjekt und Sensor zueinander zu verschieben. Daher wird eine Theorie entwickelt, unter welchen Randbedingungen bewegte Objekte von einem OPLM-Messsystem aufgelöst werden können. Die Theorie wird anschließend experimentell überprüft und bestätigt. Für die Auswertung der bei der Modulation der optischen Weglänge entstehenden Interferenzen existieren bereits einige erprobte Algorithmen, welche auf ihre Eignung hin untersucht und mit selbst entwickelten Algorithmen verglichen werden. Auch wird darauf eingegangen, welches die zentralen Herausforderungen bei der Planung von OPLM-Interferometern sind und wie sich insbesondere die Wahl des Aktors für die OPLM auf das gesamte Messsystem auswirkt. Bei den beiden Messsystemen werden jeweils wichtige Komponenten wie analoge Elektronik und Aktorik sowie ihre Funktionsweise erläutert. Es wird detailliert beschrieben, wie ein OPLM-Messsystem charakterisiert und kalibriert werden muss, um möglichst zuverlässige Messwerte zu liefern. Abschließend werden die Möglichkeiten der beiden entwickelten Systeme durch Beispielmessungen demonstriert, sowie ihre Messgenauigkeit charakterisiert.

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).

Random walk radiosity with generalized absorption probabilities

The author studies random walk estimators for radiosity with generalized absorption probabilities. That is, a path will either die or survive on a patch according to an arbitrary probability. The estimators studied so far, the infinite path length estimator and finite path length one, can be considered as particular cases. Practical applications of the random walks with generalized probabilities are given. A necessary and sufficient condition for the existence of the variance is given, together with heuristics to be used in practical cases. The optimal probabilities are also found for the case when one is interested in the whole scene, and are equal to the reflectivities

Reconciling the electron counterstreaming and dropout occurrence rates with the heliospheric flux budget

Counterstreaming electrons (CSEs) are treated as signatures of closed magnetic flux, i.e., loops connected to the Sun at both ends. However, CSEs at 1 AU likely fade as the apex of a closed loop passes beyond some distance R, owing to scattering of the sunward beam along its continually increasing path length. The remaining antisunward beam at 1 AU would then give a false signature of open flux. Subsequent opening of a loop at the Sun by interchange reconnection with an open field line would produce an electron dropout (ED) at 1 AU, as if two open field lines were reconnecting to completely disconnect from the Sun. Thus EDs can be signatures of interchange reconnection as well as the commonly attributed disconnection. We incorporate CSE fadeout into a model that matches time-varying closed flux from interplanetary coronal mass ejections (ICMEs) to the solar cycle variation in heliospheric flux. Using the observed occurrence rate of CSEs at solar maximum, the model estimates R ∼ 8–10 AU. Hence we demonstrate that EDs should be much rarer than CSEs at 1 AU, as EDs can only be detected when the juncture points of reconnected field lines lie sunward of the detector, whereas CSEs continue to be detected in the legs of all loops that have expanded beyond the detector, out to R. We also demonstrate that if closed flux added to the heliosphere by ICMEs is instead balanced by disconnection elsewhere, then ED occurrence at 1 AU would still be rare, contrary to earlier expectations.

Disruption of sitting balance after stroke: influence of spoken output

Objectives: To identify the extent of dual task interference between cognitive and motor tasks, (cognitive motor interference (CMI)) in sitting balance during recovery from stroke; to compare CMI in sitting balance between stroke and non-stroke groups; and to record any changes to CMI during sitting that correlate with functional recovery. Method: 36 patients from stroke rehabilitation settings in three NHS trusts. Healthy control group: 21 older volunteers. Measures of seated postural sway were taken in unsupported sitting positions, alone, or concurrently with either a repetitive utterance task or an oral word category generation task. Outcome measures were variability of sway area, path length of sway, and the number of valid words generated. Results: Stroke patients were generally less stable than controls during unsupported sitting tasks. They showed greater sway during repetitive speech compared with quiet sitting, but did not show increased instability to posture between repetitive speech and word category generation. When compared with controls, stroke patients experienced greater dual task interferences during repetitive utterance but not during word generation. Sway during repetitive speech was negatively correlated with concurrent function on the Barthel ADL index. Conclusions: The stroke patients showed postural instability and poor word generation skills. The results of this study show that the effort of verbal utterances alone was sufficient to disturb postural control early after stroke, and the extent of this instability correlated with concomitant Barthel ADL function.

Intensities and self-broadening coefficients of the strongest water vapour lines in the 2.7 and 6.25μm absorption bands

Intensities and self-broadening coefficients are presented for about 460 of the strongest water vapour lines in the spectral regions 1400–1840 cm−1 and 3440–3970 cm−1 at room temperature, obtained from rather unique measurements using a 5-mm-path-length cell. The retrieved spectral line parameters are compared with those in the HITRAN database ver. 2008 and 2012 and with recent ab-initio calculations. Both the retrieved intensities and half-widths are on average in reasonable agreement with those in HITRAN-2012. Maximum systematic differences do not exceed 4% for intensities (1600 cm−1 band) and 7% for self-broadening coefficients (3600 cm−1 band). For many lines however significant disagreements were detected with the HITRAN-2012 data, exceeding the average uncertainty of the retrieval. In addition, water vapour line parameters for 5300 cm−1 (1.9 μm) band reported by us in 2005 were also compared with HITRAN-2012, and show average differences of 4–5% for both intensities and half-widths.

Investigating relationships within and between category networks in Wikipedia

This work maps and analyses cross-citations in the areas of Biology, Mathematics, Physics and Medicine in the English version of Wikipedia, which are represented as an undirected complex network where the entries correspond to nodes and the citations among the entries are mapped as edges. We found a high value of clustering coefficient for the areas of Biology and Medicine, and a small value for Mathematics and Physics. The topological organization is also different for each network, including a modular structure for Biology and Medicine, a sparse structure for Mathematics and a dense core for Physics. The networks have degree distributions that can be approximated by a power-law with a cut-off. The assortativity of the isolated networks has also been investigated and the results indicate distinct patterns for each subject. We estimated the betweenness centrality of each node considering the full Wikipedia network, which contains the nodes of the four subjects and the edges between them. In addition, the average shortest path length between the subjects revealed a close relationship between the subjects of Biology and Physics, and also between Medicine and Physics. Our results indicate that the analysis of the full Wikipedia network cannot predict the behavior of the isolated categories since their properties can be very different from those observed in the full network. (C) 2011 Elsevier Ltd. All rights reserved.

On the efficiency of data representation on the modeling and characterization of complex networks

Specific choices about how to represent complex networks can have a substantial impact on the execution time required for the respective construction and analysis of those structures. In this work we report a comparison of the effects of representing complex networks statically by adjacency matrices or dynamically by adjacency lists. Three theoretical models of complex networks are considered: two types of Erdos-Renyi as well as the Barabasi-Albert model. We investigated the effect of the different representations with respect to the construction and measurement of several topological properties (i.e. degree, clustering coefficient, shortest path length, and betweenness centrality). We found that different forms of representation generally have a substantial effect on the execution time, with the sparse representation frequently resulting in remarkably superior performance. (C) 2011 Elsevier B.V. All rights reserved.

Thermo-optics parameters measurements in photorefractive sillenite Bi(12)SiO(20) crystals by thermal lens technique

The present work reports on the thermo-optical properties of photorefractive sillenite Bi(12)SiO(20) (BSO) crystals obtained by applying the Thermal Lens Spectrometry technique (TLS). This crystals presents one high photorefractive sensitivity in the region blue-green spectra, since the measurements were carried out at two pump beam wavelengths (514.5 nm and 750 nm) to study of the light-induced effects in this material (thermal and/or photorefractive). We determine thermo-optical parameters like thermal diffusivity (D), thermal conductivity (K) and temperature coefficient of the optical path length change (ds/dT) in sillenite crystals. These aspects, for what we know, not was studied in details up to now using the lens spectrometry technique and are very important against of the promising potentiality of applications these crystals in non linear optics, real time holography and optical processing data.

Thermal lens spectrometry in pyroelectric lithium niobate crystals

In this work, the light-induced lens effect due to thermal and/or photorefractive processes was studied in pyroelectric (undoped and Fe(2+)-doped) lithium niobate crystals (LiNbO(3)) using thermal lens spectrometry with a two-beam (pump-probe) mode-mismatched configuration. The measurements were carried out at two pump beam wavelengths (514.5 and 750 nm) to establish a full understanding of the present effects in this material (thermal and/or photorefractive). We present an easy-to-implement method to determine quantitative values of the pyroelectric coefficient (dPs/dT), its contribution to the thermal effect and other thermo-optical parameters like thermal diffusivity (D), thermal conductivity (K) and temperature coefficient of the optical path length change (ds/dT). These measurements were performed in LiNbO(3) and LiNbO(3): Fe (0.1 ppm Fe(2+)) crystals with c axis along the direction of laser propagation.

Resilience of protein-protein interaction networks as determined by their large-scale topological features

The relationship between the structure and function of biological networks constitutes a fundamental issue in systems biology. Particularly, the structure of protein-protein interaction networks is related to important biological functions. In this work, we investigated how such a resilience is determined by the large scale features of the respective networks. Four species are taken into account, namely yeast Saccharomyces cerevisiae, worm Caenorhabditis elegans, fly Drosophila melanogaster and Homo sapiens. We adopted two entropy-related measurements (degree entropy and dynamic entropy) in order to quantify the overall degree of robustness of these networks. We verified that while they exhibit similar structural variations under random node removal, they differ significantly when subjected to intentional attacks (hub removal). As a matter of fact, more complex species tended to exhibit more robust networks. More specifically, we quantified how six important measurements of the networks topology (namely clustering coefficient, average degree of neighbors, average shortest path length, diameter, assortativity coefficient, and slope of the power law degree distribution) correlated with the two entropy measurements. Our results revealed that the fraction of hubs and the average neighbor degree contribute significantly for the resilience of networks. In addition, the topological analysis of the removed hubs indicated that the presence of alternative paths between the proteins connected to hubs tend to reinforce resilience. The performed analysis helps to understand how resilience is underlain in networks and can be applied to the development of protein network models.

Development of a sequential injection chromatography (SIC) method for determination of simazine, atrazine, and propazine

This paper describes the development of a sequential injection chromatography (SIC) procedure for separation and quantification of the herbicides simazine, atrazine, and propazine exploring the low backpressure of a 2.5 cm long monolithic C(18) column. The separation of the three compounds was achieved in less than 90 s with resolution > 1.5 using a mobile phase composed by ACN/1.25 mmol/L acetate buffer (pH 4.5) at the volumetric ratio of 35:65 and flow rate of 40 mu L/s. Detection was made at 223 nm using a flow cell with 40 mm of optical path length. The LOD was 10 mu g/L for the three triazines and the quantification limits were of 30 mu g/L for simazine and propazine and 40 mu g/L for atrazine. The sampling frequency is 27 samples per hour, consuming 1.1 mL of ACN per analysis. The proposed methodology was applied to spiked water samples and no statistically significant differences were observed in comparison to a conventional HPLC-UV method. The major metabolites of atrazine and other herbicides did not interfere in the analysis, being eluted from the column either together with the unretained peak, or at retention times well-resolved from the studied compounds.