Entity Linking for Web Search Queries

We consider the problem of linking web search queries to entities from a knowledge base such as Wikipedia. Such linking enables converting a user’s web search session to a footprint in the knowledge base that could be used to enrich the user profile. Traditional methods for entity linking have been directed towards finding entity mentions in text documents such as news reports, each of which are possibly linked to multiple entities enabling the usage of measures like entity set coherence. Since web search queries are very small text fragments, such criteria that rely on existence of a multitude of mentions do not work too well on them. We propose a three-phase method for linking web search queries to wikipedia entities. The first phase does IR-style scoring of entities against the search query to narrow down to a subset of entities that are expanded using hyperlink information in the second phase to a larger set. Lastly, we use a graph traversal approach to identify the top entities to link the query to. Through an empirical evaluation on real-world web search queries, we illustrate that our methods significantly enhance the linking accuracy over state-of-the-art methods.

A Molecular Mechanism for Sequential Activation of a G Protein-Coupled Receptor

Ligands targeting G protein-coupled receptors (GPCRs) are currently classified as either orthosteric, allosteric, or dualsteric/bitopic. Here, we introduce a new pharmacological concept for GPCR functional modulation: sequential receptor activation. A hallmark feature of this is a stepwise ligand binding mode with transient activation of a first receptor site followed by sustained activation of a second topographically distinct site. We identify 4-CMTB (2-(4-chlorophenyl)-3-methyl-N-(thiazol-2-yl)butanamide), previously classified as a pure allosteric agonist of the free fatty acid receptor 2, as the first sequential activator and corroborate its two-step activation in living cells by tracking integrated responses with innovative label-free biosensors that visualize multiple signaling inputs in real time. We validate this unique pharmacology with traditional cellular readouts, including mutational and pharmacological perturbations along with computational methods, and propose a kinetic model applicable to the analysis of sequential receptor activation. We envision this form of dynamic agonism as a common principle of nature to spatiotemporally encode cellular information.

Compact Routing Messages in Self-Healing Trees

Existing compact routing schemes, e.g., Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013], often have no means to tolerate failures, once the system has been setup and started. This paper presents, to our knowledge, the first self-healing compact routing scheme. Besides, our schemes are developed for low memory nodes, i.e., nodes need only O(log2 n) memory, and are thus, compact schemes.
We introduce two algorithms of independent interest: The first is CompactFT, a novel compact version (using only O(log n) local memory) of the self-healing algorithm Forgiving Tree of Hayes et al. [PODC 2008]. The second algorithm (CompactFTZ) combines CompactFT with Thorup-Zwick’s treebased compact routing scheme [SPAA 2001] to produce a fully compact self-healing routing scheme. In the self-healing model, the adversary deletes nodes one at a time with the affected nodes self-healing locally by adding few edges. CompactFT recovers from each attack in only O(1) time and ∆ messages, with only +3 degree increase and O(log∆) graph diameter increase, over any sequence of deletions (∆ is the initial maximum degree).
Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver has not been deleted, with only an additional O(y log ∆) latency, where y is the number of nodes that have been deleted on the path between s and t. If t has been deleted, s gets informed and the packet removed from the network.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

F. G. Teixeira e a comunidade matemática europeia nos séculos XIX-XX

Esta dissertação descreve o processo de integração dos matemáticos portugueses na comunidade matemática internacional no final do século XIX e início do século XX, focando-se na vida e obra do matemático Francisco Gomes Teixeira (1851-1933). Tenciona a ser mais um contributo para o reconhecimento nacional e internacional do matemático Gomes Teixeira analisando a sua obra como matemático e organizador científico em Portugal através de fontes, parcialmente ainda não conhecidas. Para esse efeito analisou-se a evolução histórica que ocorreu no mundo científico daquela época, em particular a formação da comunidade matemática através de iniciativas individuais ou coletivas, muitas vezes acompanhadas pela fundação de revistas e elaboração de manuais que contribuíram para a internacionalização e, de certa forma, para uma estandardização do estudo universitário básico. Em particular foi estudada a situação em Portugal, onde o papel de liderança foi assumido por Gomes Teixeira. Mostra-se como Gomes Teixeira, graças ao seu trabalho, ao seu talento como matemático e à sua atividade como organizador académico, conseguiu reduzir significativamente o isolamento científico de Portugal na área da matemática. Estudou-se em extensão a fundação de revistas científicas em diferentes países, acompanhando a sua evolução desde de revistas nacionais até revistas internacionais. Focando-nos no Jornal de Sciencias Matemáticas e Astronómicas, fundado em 1877 por Gomes Teixeira (mais tarde conhecido internacionalmente como Teixeira’s Journal), acompanhamos detalhadamente a sua transformação de uma revista nacional numa revista internacional, sendo esta transformação comum naquela época à maioria de revistas científicas importantes de outros países como, por exemplo, no caso do Jornal de Crelle, do Jornal de Liouville, ou outros. Estudou-se igualmente o reconhecimento a nível internacional, através de referências estrangeiras, da abordagem original de Gomes Teixeira à Análise Infinitesimal patente nos seus manuais. O interesse de Gomes Teixeira pela teoria das funções analíticas e pelos seus diferentes desenvolvimentos em série manifestou-se no grande número de artigos publicados sobre este tema e encontrou reconhecimento justo pela designação de um teorema que completa resultados de Lagrange e de Laurent como Teorema de Teixeira. Na sua análise do mérito científico de Gomes Teixeira esta dissertação restringiu-se conscientemente nesta área da Análise Matemática, uma vez que um estudo abrangente de toda a obra ultrapassasse o nosso objetivo. Foi também discutido o intenso intercâmbio científico levado a cabo por Gomes Teixeira através de correspondência e troca de publicações ou permuta de revistas com os matemáticos de diferentes países. Esta análise permitiu verificar um aumento da popularidade dos matemáticos portugueses através do incremento do número de artigos publicados no estrangeiro durante quase 30 anos. Uma fonte imprescindível nesta análise foi o Jahrbuch über die Fortschritte der Mathematik, cujas referências (em geral na língua alemã e por isso até agora quase nunca usadas na literatura Portuguesa) documentaram as publicações em quase todas as revistas matemáticas durante os anos da sua existência entre 1868 e 1942. Descreve-se a colaboração de Gomes Teixeira com diferentes organizações internacionais e documenta-se o apreço internacional por parte do mundo académico. Novos documentos traçam o processo de eleição como membro da Academia das Ciências Alemã Leopoldina, sob proposta de Georg Cantor e outros matemáticos alemães. Finalmente, incluí-se uma breve descrição das atividades levadas a cabo na Rússia, em Espanha e na Grécia em prol do processo de internacionalização da comunidade matemática europeia tendo em vista uma melhor contextualização do contributo de Gomes Teixeira para a integração de Portugal neste processo.

Necessary and sufficient conditions for a Hamiltonian graph

A graph is singular if the zero eigenvalue is in the spectrum of its 0-1 adjacency matrix A. If an eigenvector belonging to the zero eigenspace of A has no zero entries, then the singular graph is said to be a core graph. A ( k,t)-regular set is a subset of the vertices inducing a k -regular subgraph such that every vertex not in the subset has t neighbours in it. We consider the case when k=t which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a ( k,k )-regular set, then it is a core graph. By considering the walk matrix we develop an algorithm to extract ( k,k )-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.

Spectra of graphs obtained by a generalization of the join graph operation

Taking a Fiedler’s result on the spectrum of a matrix formed from two symmetric matrices as a motivation, a more general result is deduced and applied to the determination of adjacency and Laplacian spectra of graphs obtained by a generalized join graph operation on families of graphs (regular in the case of adjacency spectra and arbitrary in the case of Laplacian spectra). Some additional consequences are explored, namely regarding the largest eigenvalue and algebraic connectivity.

Relations between (κ, τ)-regular sets and star complements

Let G be a finite graph with an eigenvalue μ of multiplicity m. A set X of m vertices in G is called a star set for μ in G if μ is not an eigenvalue of the star complement G\X which is the subgraph of G induced by vertices not in X. A vertex subset of a graph is (k ,t)-regular if it induces a k -regular subgraph and every vertex not in the subset has t neighbors in it. We investigate the graphs having a (k,t)-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples.