I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their weights is maximum (The weights are positive), under the constraint that every pair is not connected by an edge, i.e $\forall\ v_i,v_j \in S:(v_i,v_j) \not\in E$.
A common problem instance would be a graph with around $2 \times 10^5$ nodes, up to around $5 \times 10^5$. The degree of a node is bounded by ~$100$, and the number of edges will be around $10^6$.
Can anyone recommend a heuristic algorithm for finding a near-optimal solution? A runtime of hours or even days is acceptable.
I've been looking so far at articles about Tabu search and that is the current direction I am going towards.