Graph coloring, minimum-diameter partitioning, and the analysis of confusion matrices

It is well known that minimum-diameter partitioning of symmetric dissimilarity matrices can be framed within the context of coloring the vertices of a graph. Although confusion data are typically represented in the form of asymmetric similarity matrices, they are also amenable to a graph-coloring perspective. In this paper, we propose the integration of the minimum-diameter partitioning method with a neighborhood-based coloring approach for analyzing digraphs corresponding to confusion data. This procedure is capable of producing minimum-diameter partitions with the added desirable property that vertices with the same color have similar in-neighborhoods (i.e., directed edges entering the vertex) and out-neighborhoods (i.e., directed edges exiting the vertex) for the digraph corresponding to the minimum partition diameter.     

Neuroscience today,Florence 25–27 March 2007: foreword

Currently in humor research, there exists a dearth of computational models for humor perception. The existing theories are not quantifiable and efforts need to be made to quantify the models and incorporate neuropsychological findings in humor research. We propose a new computational model (GraPHIA) for perceiving phonological jokes or puns. GraPHIA consists of a semantic network and a phonological network where words are represented by nodes in both the networks. Novel features based on graph theoretical concepts are proposed and computed for the identification of homophonic jokes. The data set for evaluating the model consisted of homophonic puns, normal sentences, and ambiguous nonsense sentences. The classification results show that the feature values result in successful identification of phonological jokes and ambiguous nonsense sentences suggesting that the proposed model is a plausible model for humor perception. Further work is needed to extend the model for identification of other types of phonological jokes.

Patterns of Response Times and Response Choices to Science Questions: The Influence of Relative Processing Time

We report on five experiments investigating response choices and response times to simple science questions that evoke student “misconceptions,” and we construct a simple model to explain the patterns of response choices. Physics students were asked to compare a physical quantity represented by the slope, such as speed, on simple physics graphs. We found that response times of incorrect answers, resulting from comparing heights, were faster than response times of correct answers comparing slopes. This result alone might be explained by the fact that height was typically processed faster than slope for this kind of task, which we confirmed in a separate experiment. However, we hypothesize that the difference in response time is an indicator of the cause (rather than the result) of the response choice. To support this, we found that imposing a 3‐s delay in responding increased the number of students comparing slopes (answering correctly) on the task. Additionally a significant proportion of students recognized the correct written rule (compare slope), but on the graph task they incorrectly compared heights. Finally, training either with repetitive examples or providing a general rule both improved scores, but only repetitive examples had a large effect on response times, thus providing evidence of dual paths or processes to a solution. Considering models of heuristics, information accumulation models, and models relevant to the Stroop effect, we construct a simple relative processing time model that could be viewed as a kind of fluency heuristic. The results suggest that misconception‐like patterns of answers to some science questions commonly found on tests may be explained in part by automatic processes that involve the relative processing time of considered dimensions and a priority to answer quickly.     

The temporal organization of functional brain connectivity is abnormal in schizophrenia but does not correlate with symptomatology

Previous work employing graph theory and nonlinear analysis has found increased spatial and temporal disorder, respectively, of functional brain connectivity in schizophrenia. We present a new method combining graph theory and nonlinear techniques that measures the temporal disorder of functional brain connections. Multichannel electroencephalographic data were windowed and functional networks were reconstructed using the minimum spanning trees of correlation matrices. Using a method based on Shannon entropy, we found elevated connection entropy in gamma activity of patients with schizophrenia; however, gamma connection entropy remained elevated in patients with schizophrenia even after a reduction in symptoms due to treatment with antipsychotics. Our results are consistent with several possibilities: (1) aberrant functional connectivity is epiphenomenal to schizophrenia, (2) aberrant functional connectivity is a central feature but antipsychotics reduce symptoms by an independent mechanism, or (3) connection entropy is not an appropriately sensitive measure of brain abnormalities in schizophrenia.     

The monadic second-order logic of graphs XV: On a conjecture by D. Seese

A conjecture by D. Seese states that if a set of graphs has a decidable monadic second-order theory, then it is the image of a set of trees under a transformation of relational structures defined by monadic second-order formulas, or equivalently, has bounded clique-width. We prove that this conjecture is true if and only if it is true for the particular cases of bipartite undirected graphs, of directed graphs, of partial orders and of comparability graphs. We also prove that it is true for line graphs, for interval graphs and for partial orders of dimension 2. Our treatment of certain countably infinite graphs uses a representation of countable linear orders by binary trees that can be constructed by monadic second-order formulas. By using a counting argument, we show the intrinsic limits of the methods used here to handle this conjecture.     

Graph‐Theoretic Properties of Networks Based on Word Association Norms: Implications for Models of Lexical Semantic Memory

We compared the ability of three different contextual models of lexical semantic memory (BEAGLE, Latent Semantic Analysis, and the Topic model) and of a simple associative model (POC) to predict the properties of semantic networks derived from word association norms. None of the semantic models were able to accurately predict all of the network properties. All three contextual models over‐predicted clustering in the norms, whereas the associative model under‐predicted clustering. Only a hybrid model that assumed that some of the responses were based on a contextual model and others on an associative network (POC) successfully predicted all of the network properties and predicted a word's top five associates as well as or better than the better of the two constituent models. The results suggest that participants switch between a contextual representation and an associative network when generating free associations. We discuss the role that each of these representations may play in lexical semantic memory. Concordant with recent multicomponent theories of semantic memory, the associative network may encode coordinate relations between concepts (e.g., the relation between pea and bean, or between sparrow and robin), and contextual representations may be used to process information about more abstract concepts.     

Sort out your neighbourhood

Axelrod (The evolution of cooperation, 1984) and others explain how cooperation can emerge in repeated 2-person prisoner’s dilemmas. But in public good games with anonymous contributions, we expect a breakdown of cooperation because direct reciprocity fails. However, if agents are situated in a social network determining which agents interact, and if they can influence the network, then cooperation can be a viable strategy. Social networks are modelled as graphs. Agents play public good games with their neighbours. After each game, they can terminate connections to others, and new connections are created. Cooperative agents do well because they manage to cluster with cooperators and avoid defectors. Computer simulations demonstrate that group formation and exclusion are powerful mechanisms to promote cooperation in dilemma situations. This explains why social dilemmas can often be solved if agents can choose with whom they interact.     

Prenatal exposure to maternal depression is related to the functional connectivity organization underlying emotion perception in 8-10-month-old infants – Preliminary findings

Emotion perception is critical for infant’s social development. Mother’s mood during pregnancy has been associated with infants’ emotional developmental risks. Graphtheory analysis was applied on EEG data recorded from 35, 8-to-10-month-old-infants prenatally exposed to high or low depressed symptoms, while viewing happy and sad faces. We found an interaction between group and emotion such that infants exposed to high-depressed-symptoms showed higher modularity – reflecting reduced perceptual-dynamics - for viewing happy emotions compared to sad. The opposite was observed for infants exposed to low-depressive-symptoms. These preliminary findings suggest that prenatal depressive mood may shape early functional organization for viewing emotional faces.     

Functional connectivity abnormalities during contextual processing in schizophrenia and in Parkinson’s disease

Functional connectivity was evaluated in patients with schizophrenia (SC) and in patients with Parkinson’s disease (PD) during the performance of a local contextual processing paradigm, to investigate the proposition that functional disconnection is involved with contextual processing deficits in these populations. To this end, we utilized event-related EEG signals, synchronization likelihood and graph theoretical analysis. Local context was defined as the occurrence of a predictive sequence of stimuli before the presentation of a target event. In the SC patients, we observed a decrease in path length (L) in the beta band, for the predictive sequence and for predicted and random targets, compared with controls. These abnormalities were associated with weaker frontal-temporal-parietal connections. In the PD patients we found longer L (theta band) for predicted targets, and higher cluster coefficients for both the predictive sequence (theta band) and predicted targets (alpha and theta bands), compared with controls. Detection of predicted targets was associated with weaker frontal-parietal connections in PD. No group differences were found for randomized standard stimuli in both SC and PD patients. These findings provide evidence of task-specific functional connectivity abnormalities within frontal networks during local contextual processing.