Given that oncology patients experience an average of 14 co-occurring symptoms, the identification of sentinel or core symptoms is a critical need for effective symptom management. However, this task is an extremely challenging one. To address this need, we used Bayesian Network Analysis (BNA) approaches on a comprehensive dataset of 38 distinct and co-occurring cancer symptoms from a sample of 1328 cancer patients receiving chemotherapy. We evaluate three classes of algorithms (constrained-based, score-based, hybrid algorithms) on their structural stability and performance with different sample sizes and demographic characteristics (gender and age). We demonstrate their potential clinical use for casual discovery and inference. The hybrid algorithm identified more dense network structures that were clinically relevant, not only for the entire sample but for our case studies of gender and age. Our work demonstrates how to process a comprehensive set of symptom experience data for interactions and provides valuable information on the use of BNA in clinical practice when different algorithms, sample sizes and comparative sub-groups are evaluated.