Cell-cell interaction (CCI) networks are key to understanding disease progression and treatment response. However, existing methods for inferring these networks often aggregate data across patients or focus on cell-type level interactions, providing a generalized overview but overlooking patient heterogeneity and local network structures. To address this, we introduce "random cell-cell interaction generator" (RaCInG), a model based on random graphs to derive personalized networks leveraging prior knowledge on ligand-receptor interactions and bulk RNA sequencing data. We applied RaCInG to 8,683 cancer patients to extract 643 network features related to the tumor microenvironment and unveiled associations with immune response and subtypes, enabling prediction and explanation of immunotherapy responses. RaCInG demonstrated robustness and showed consistencies with state-of-the-art methods. Our findings highlight RaCInG's potential to elucidate patient-specific network dynamics, offering insights into cancer biology and treatment responses. RaCInG is poised to advance our understanding of complex CCI s in cancer and other biomedical domains.