Peter Chin

Sie Hendrata Dharmawan, Kevin Limanta, Brendan Liu et al.

Node centrality is a fundamental problem in network analysis, yet classical metrics fail to capture the collective, coalitional nature of influence. We present a systematic empirical evaluation of the Shapley-value-based framework for the sphere of influence problem -- selecting $m$ nodes to maximize network coverage under three reachability criteria: single-hop, $k$-hop, and multi-path connectivity -- using exact polynomial-time algorithms due to Michalak et al. Evaluation across three diverse real-world networks (Euroroad, Facebook TV Shows, and Cora) demonstrates that practical approximation ratios consistently approach 0.9, substantially exceeding the theoretical $(1-1/e)$ lower bound, and that the Shapley-based approach dramatically outperforms a degree-based baseline, particularly in hub-and-spoke topologies. In the most striking case, Shapley-based selection identifies just 26 nodes (under 1\% of the Cora network) sufficient to influence half the graph under 3-hop reachability, compared to substantially larger sets required by the naive baseline.

Mateusz Nowak, Xavier Cadet, Peter Chin

Multiple-choice question (MCQ) benchmarks have been a standard evaluation practice for measuring LLMs' ability to reason and answer knowledge-based questions. Through a synthetic NonsenseQA benchmark, we observe that different LLMs exhibit varying degrees of label-position-few-shot-prompt bias, where the model either uses the answer position, the label in front of the answer, the distributions of correct answers present in the few-shot prompt, or a combination of all to answer each MCQ question. We propose a simple bias-reduced evaluation protocol that replaces the labels of each question with uniform, unordered labels and prompts the LLM to use the whole answer presented. With a simple sentence similarity model, we demonstrate improved robustness and lower standard deviation between different permutations of answers with a minimal drop in LLM's performance, exposing the LLM's capabilities under reduced evaluation artifacts, without any help from the prompt examples or the option labels. Across multiple benchmarks and models, this protocol substantially improves the robustness to answer permutations, reducing mean accuracy variance $3\times$ with only a minimal decrease in the mean model's performance. Through ablation studies on various embedding models and similarity functions, we show that the method is more robust than the standard ones.

Sie Hendrata Dharmawan, Peter Chin

We propose a streamlined spectral algorithm for community detection in the two-community stochastic block model (SBM) under constant edge density assumptions. By reducing algorithmic complexity through the elimination of non-essential preprocessing steps, our method directly leverages the spectral properties of the adjacency matrix. We demonstrate that our algorithm exploits specific characteristics of the second eigenvalue to achieve improved error bounds that approach information-theoretic limits, representing a significant improvement over existing methods. Theoretical analysis establishes that our error rates are tighter than previously reported bounds in the literature. Comprehensive experimental validation confirms our theoretical findings and demonstrates the practical effectiveness of the simplified approach. Our results suggest that algorithmic simplification, rather than increasing complexity, can lead to both computational efficiency and enhanced performance in spectral community detection.